|
Introduction Complexity The Art-Gallery The Proofs Conclusions References |
Conclusions on the NP-Completeness at the Art GalleryThus, it seems that unless P is equal to NP (which is believed to be false by many, including the author) then there is no efficient way to find the optimal guarding of a polygon. Though this does not really effect real-life art galleries, there are many applications which suffer from this problem's intractability including problems in visibity and optimization. An interesting question is whether or not there are heuristics to approximate the solution with bounded error. The trivial triangulation and 3-color algorithm will always yield a linear error which is already quite good. Any algorithm that breaks a polygon into convex pieces will also yield an excellent approximation depending on it's output bound. Any reader who finds results on polygon partitioning or on optimal guard placement heuristics is encouraged to email the author. |