1985/01/01 by Teofilo F. Gonzalez, Si-Qing Zheng · 1 citation
Computer Science · Engineering · #Computational Geometry and Mesh Generation #VLSI and FPGA Design Techniques #Digital Image Processing Techniques
paper · pdf · doi:10.1145/323233.323269
openalex publication_date 1985/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.