Tag Archives: NP-completeness

Minimum edge length partitioning of rectilinear polygons

Figure 10 from Minimum Edge Length Partitioning of Rectilinear Polygons by Lingas et al., 1982.

The title of this blog post is the same as that of a seminal paper in computational geometry and VLSI design by Lingas, Pinter, Rivest and Shamir from 1982.  The authors present an O(n^4) algorithm to produce a minimum-length rectangular partitioning of a rectilinear polygon without holes.  (A rectilinear polygon, also called an orthogonal polygon, is one whose sides are all axis-parallel, i.e., all either “horizontal” or “vertical.”)  They also prove the NP-completeness of the same optimization problem in the case where the rectilinear polygon has rectilinear holes.

Variations of this problem come up all the time in VLSI design.  There have been many subseqent papers on approximation algorithms, faster methods for tractable cases, and so on.  The Handbook of Discrete and Computational Geometry has a survey of known results in Chapter 26.  However, I recently needed to review the original NP-completeness proof, and apparently it exists nowhere online.  Dozens of papers (and books) cite the result, but no one seems to reprove it, and it did not appear in a journal with an online archive.  I took the liberty of scanning it, so it would be available for download somewhere (pdf file here: MinimumEdgeLengthPartitioningOfRectilinearPolygons), and with the blog post’s title identical to the article’s title, I hope that anyone searching for it in future might find this link without much effort.

Continue reading

Advertisements