Approximation algorithms for partitioning a rectangle with interior points (Q1263970): Difference between revisions

The article addresses the problem of partitioning a rectilinear polygon into rectangles by introducing a set of line segments (edges) of least total length. Several variations of this problem were shown to be NP- hard, but the computational complexity of some related problems remains unknown. Particularly, the authors present an efficient approximation algorithm for the case where a set of points inside rectilinear polygon is also given and a valid partition must not contain points from this set. The solutions generated by the algorithm are guaranteed to be within three times the optimal solution value. The method used is transformation of a given instance into an instance of another variation of the problem, which we know to solve in polynomial time. It is shown that this approach guarantees abovementioned bounds of approximation.