Checking a Guarding for the Art Gallery Problem 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
 A: 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. 
A: 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.
