Bounds for partitioning rectilinear polygons

Abstract

We study the problem of partitioning a rectilinear polygon with interior points into rectangles by introducing a set of line segments. All points must be included in at least one of the line segments introduced and the objective function is to introduce a set of line segments such that the sum of their lengths is minimal. Since this problem is computationally intractable, we present efficient approximation algorithms for its solution. The solutions generated by our algorithms are guaranteed to be within a fixed constant of the optimal solution value. Even though the constant approximation bound is not so small, we conjecture that in general the solutions our algorithms generate are close to optimal.