Checking a Guarding for the Art Gallery Problem

Question

In the Art Gallery Problem, we have given a polygon $P$ on $n$ vertices and a number $k$ and we want to know if there exists $k$ guards such that every point inside the polygon is seen by at least one of the guards. We say a point $p$ sees a point $q$ if the entire segment $pq$ is contained inside $P$. Let us assume here that we are in the real RAM model of computation. (i.e., we can add multiply etc. real numbers.)

Here, I am interested in polygons with and without holes.

Now, the problem is known to be ETR-complete. Which essentially means, that we cannot even guess in NP-time a correct set of guards.

But let us say that I have given some set of $k$ guards, by their coordinates and all I want to do is checking that they guard correctly the entire polygon.

Obviously, this can be done in polynomial time. But what is the currently best known running time? I would like to see something like $O(k^2n^2)$. But I would hope things might run a little faster than that.

I would very much appreciate a source that I can cite!

many thanks Till

Answer 1

I have found an algorithm in the literature [1] running in $O(kn\log n \log k)$ time.

I briefly repeat the argument.

Compute the visibility region of each guard in $O(n)$ time. (total = $O(kn)$) Split the guarding set $G$ into two guarding set $G_1 \cup G_2$ of roughly equal size. Recursively compute the visibility regions of $G_1$ and $G_2$ and then take the union using a line sweep argument. Each visibility region of any $F\subseteq G$ with $|F| = l$ has complexity $O(nl + l^2)$ by [2]. Thus we get the recursion: $T(n,k) \leq T(n,k/2) + O(nl\log nl)$ This yields the running time.

---

Can this be improved? Probably not by much. A proof would be nice.

What about polygons with holes? Can we get the same bound?

---

[1] GUARDING GALLERIES AND TERRAINS Alon Efrat and Sariel Har-Peled 2002 in Information processing letter.

[2] L. Gewali, A. Meng, Joseph S. B. Mitchell, and S. Ntafos. Path planning in 0/1/oo weighted regions with applications.

Answer 2

Thanks to Joseph O'Rourke we can do the following algorithm:

Compute $k$ visibility polygons in $O(n)$ time per visibility polygon. According to [1] a visibility region in a simple polygon can be computed in linear time and thus also has at most a linear number of edges and vertices. For polygons with $h$ holes, it is possible to compute the visibility regions in $O(n+h\log h)$ time, see [3]. Note that the number of vertices and edges of those polygons is still $O(n)$.

(Every edge of the visibility polygon has at least one vertex of the original polygon and every vertex is to exactly two edges incident.)

Then we have in total $m = O(kn)$ edges and vertices, in either case.

We can compute then the union $Q$ of all those polygons in $O(m\log m + l)$ time, where $l = O(m^2) = O(k^2 n^2)$ is the total number of edge intersections of all the given edges. See the Stackexchange entry also from Joseph O'Rourke [2].

Thereafter, we can check if the set of vertices of $Q$ are the same (in the same order) as the vertices of our original polygon $P$. This can be done in linear time.

The running time is dominated by $O(k^2n^2)$, by taking the union of polygons.

Is this really the best we can do??

Note that the output size is O(n).

thanks Till

[1] Joe, Barry; Simpson, R. B. (1987). "Corrections to Lee's visibility polygon algorithm". BIT Numerical Mathematics. 27 (4): 458–473. doi:10.1007/BF01937271.

[2] https://math.stackexchange.com/questions/15815/how-to-union-many-polygons-efficiently

[3] Heffernan, Paul; Mitchell, Joseph (1995). "An optimal algorithm for computing visibility in the plane". SIAM Journal on Computing. 24 (1): 184–201. doi:10.1137/S0097539791221505.