Art Gallery Problems

Tamás Róbert Mezei

My research interests include Graph Theory, Computational Geometry, and Algorithms


Mobile vs. point guards

We study the problem of guarding orthogonal art galleries with horizontal mobile guards (alternatively, vertical) and point guards, …

Extremal solutions to some art gallery and terminal-pairability problems

The thesis consists of two parts. In both parts, the problems studied are of significant interest, but are either NP-hard or unknown to …

Partitioning orthogonal polygons into at most 8-vertex pieces, with application to an art gallery theorem

We prove that every simply connected orthogonal polygon of $n$ vertices can be partitioned into $\lfloor\frac{3n+4}{16}\rfloor$ (simply …


A linear time 8/3-approximation for $r$-star guards in simple orthogonal art galleries

We study the problem of covering simple orthogonal art galleries with rectangular stars. The problem has been shown to be polynomial by …

Doctoral Dissertation Defense

Commitee: András Gyárfás, Frank Hoffmann, Károly Böröczky (chair), Ervin Győri (supervisor, non-voting)

Mobile vs. point guards in orthogonal art gallery theorems

Our results are concerned with art gallery theorems on orthogonal polygons. We prove that an n-vertex orthogonal polygon can be …

Art gallery theorems

Art gallery theorems are concerned with the number of guards required to control a polygon, and many variations exist depending on how …