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

Algorithm Engineering, pp. 379-417. Springer, Cham, 2016. $\endgroup$ – Joseph O'Rourke Aug 20 '18 at 23:05