Inapproximability of some art gallery problems.
Stephan Eidenbenz, Christoph Stamm, Peter Widmayer · 1998
We prove that the three art gallery problems Vertex Guard Edge Guard and Point Guard for simple polygons with holes cannot be approximated by any polynomial time algorithm with a ratio of lnn for any unless NP TIMEn Olog logn We obtain our results by extending and modifying the concepts of a construction introduced in Eide