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.

I will now sketch the NP-completeness proof.  It will help to look at Figures 10-14 (in the downloadable file) during the next few paragraphs.

The argument reduces the minimum-length rectangular partition problem to Planar 3-SAT.  3-SAT is the well known NP-complete problem in which you are trying to determine if a logical sentence can have the value TRUE, and each clause in the sentence contains three variables.  The implication graph of a such a logical sentence is a bipartite graph where variables are on one side, clauses are on the other, and there is an edge between variable x and clause C iff x is contained in clause C.  Planar 3-SAT as used in this paper takes as input the set of formulas for which this implication graph is a planar graph.  So a given variable can only appear in clauses that are close to each other, so to speak, otherwise edges in the implication graph would necessarily cross.  This restricted satisfiability problem is still NP-complete.  (Actually, this version of Planar 3-SAT is slightly that the typical one: usually edges between neighboring variables is required as well.  That’s not needed for the proof at hand, though.)

The authors start with an instance of Planar 3-SAT, and transform it into a rectangular partitioning problem.  If the interior of a corrugated wire is partitioned optimally by all-vertical lines, this is considered to have value “0″; if it partitioned optimally by all-horizontal lines, it is considered to have value “1″.  A wire can be partitioned optimally either way, but not with a mix of horizontal and vertical lines.  Three wires meet one another at a “clause junction.”  (In today’s terminology, we would probably call this a “clause gadget.”)  The junction is designed so that, if all three wires feed into it with vertical decompositions, the optimal decomposition inside the clause junction will be of strictly greater length than if any (or all) of the wires feeding in has horizontal decomposition.  So a clause junction is an OR device; it produces minimal-length decomposition exactly when at least one of its inputs is 1.

But wait, you might say.  What if a negation is inside a clause?  Well, there are “inverter” devices, that transform a vertical decomposition into a horizontal decomposition, and vice versa.  And, in case a variable appears in more than one clause, there is a wire-splitter device.  To complete the construction, there is a “phase shifter,” that ensures everything will line up perfectly.  So, if you could find the minimal-length rectangle partition of such a structure, you could solve the underlying instance of Planar 3-SAT.  So the rectangular partitioning optimization is NP-hard.  On the other hand, the construction of the wires and junctions can be done in time polynomial in the size of the Planar 3-SAT formula.  So the problem is NP-complete.

Ingenious.  I had to take a look at this 29-year-old paper because of something related-but-new I was trying to prove NP-complete.  I’ll post about that at some point, but, in the meantime, I wonder how many of these papers have fallen into similar disuse.  They prove things “everybody knows,” but almost no one knows how those proofs go.

Andrzej Lingas, Ron Y. Pinter, Ronald R. Rivest, & Adi Shamir (1982). Minimum edge length partitioning of rectilinear polygons Proceedings of the 20th Allerton Conference on Communication, 53-63

About these ads

5 responses to “Minimum edge length partitioning of rectilinear polygons

  1. Pingback: Polygon rectangulation, part 3: Minimum-length rectangulation | Nanoexplanations

  2. Great Post,

    I was also looking for this paper. But I am still not quite sure if this might help me in my current problem, I am looking for a way to partition a matrix (grid) into rectangles .. such that they all have minimum edge length. Does this O(n^4) solve this problem?

    Thanks again.

    • Hi Mohammed,

      Sorry for the delay in responding to you; I’ve been away from the blog for a bit. I’m not yet sure what you mean by a matrix (grid)? Do you mean a geometric object like a grid graph?

  3. Dear Aaron,

    Thank you for your reply. Well, I mean a 2D array (a matrix) or a 2d rectangle. A very simple polygon.

    Thanks again for your reply :)

  4. Very helpful article, and thanks for the link to the MEL-RP paper!

    You seem to start your argument with
    “The argument reduces the minimum-length rectangular partition problem to Planar 3-SAT.”
    Shouldn’t this be
    reduces Planar 3-SAT to the minimum-length rectangular partition problem?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s