NP-completeness of chromatic orthogonal art gallery problem

The chromatic orthogonal art gallery problem is a well-known problem in the computational geometry. Two points in an orthogonal polygon P see each other if there is an axis-aligned rectangle inside P contains them. An orthogonal guarding of P is k-colorable, if there is an assignment between k colors and the guards such that the visibility regions of every two guards in the same color have no intersection. The purposes of this paper are discussing the time complexity of k-colorability of orthogonal guarding and providing algorithms for the chromatic orthogonal art gallery problem. The correctness of presented solutions is proved, mathematically. Herein, the heuristic method is used that leads us to an innovative reduction, some optimal and one approximation algorithms. The paper shows that deciding k-colorability of orthogonal guarding for P is NP-complete. First, we prove that deciding 2-colorability of P is NP-complete. It is proved by a reduction from planar monotone rectilinear 3-SAT problem. After that, a reduction from graph coloring implies this is true for every fixed integer \(k\ge 2\). In the third step, we present a 6-approximation algorithm for every orthogonal simple polygon. Also, an exact algorithm is provided for histogram polygons that finds the minimum chromatic number.