5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ So far I have found a paper that has an $O(n^3)$ algorithm for approximate vertex guarding. Maybe the result can be used for the question I asked sciencedirect.com/science/article/pii/S0925772112001101 $\endgroup$ – Till Aug 20 '18 at 16:30
  • $\begingroup$ I guess you mean simple polygons? $\endgroup$ – Manfred Weis Aug 20 '18 at 17:15
  • 1
    $\begingroup$ Also relevant: de Rezende, Pedro J., Cid C. de Souza, Stephan Friedrichs, Michael Hemmer, Alexander Kröller, and Davi C. Tozoni. "Engineering art galleries." In Algorithm Engineering, pp. 379-417. Springer, Cham, 2016. $\endgroup$ – Joseph O'Rourke Aug 20 '18 at 23:05
  • $\begingroup$ What is the complexity if you simply union the $k$ visibility polygons, each of size $O(n)$? The union can be constructed by a simultaneous plane-sweep. $\endgroup$ – Joseph O'Rourke Aug 20 '18 at 23:27
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.