Polygon rectangulation, part 1: Minimum number of rectangles

Over the next few posts, I will consider problems of polygon rectangulation: given as input an orthogonal polygon (all interior angles are 90 or 270 degrees), decompose into adjacent, nonoverlapping rectangles that fully cover .  Different problems impose different conditions on what constitutes a “good” rectangulation.  Today we will discuss how to find a rectangulation with the least number of rectangles.

Polygon decomposition is a method often used in computer graphics and other fields, in order to break a (perhaps very complex) shape into lots of small manageable shapes.  Polygon triangulation may be the best-studied decomposition problem.  (When triangulating, we don’t require that the input polygon be orthogonal, and our objective is to cut the polygon into triangles according to some notion of “best” decomposition.)  There is an extensive literature on polygon rectangulation as well, because of its connection to VLSI design.  Suppose, for example, that our input represents a circuit board, and we want to subdivide the board by placing as little additional “ink” on the board as possible, in order to save money on each unit.  However, because of mechanical limitations, we can only place ink horizontally or vertically — i.e., only create rectangulations of .  Many questions in VLSI design are closely related to finding a rectangulation of minimum total length, which I will discuss in a future post.  The algorithm for minimum-length rectangulation is more complicated than the one I will present today for minimum-number-of-rectangles rectangulation, so today’s post can be considered a warm-up.

The attendees of the recent Midwest Theory Day know that Ming-Yang Kao and I found an application of rectangulation to DNA self-assembly.  I will blog about that in the new year.  The only other application of rectangulation to self-assembly that I know about is A Rectangular Partition Algorithm for Self-Assembly, by Li and Zhang, which appeared in a robotics conference.  (Readers interested in the latest Midwest Theory Day are invited to check out a “workshop report” I wrote on the CSTheory Community Blog.)

These slides (pdf format) by Derrick Stolee contain many lovely pictures about polygon rectangulation.  I think they may be a bit hard to follow all the way through as there is no “attached narrative,” but I recommend them anyway. 🙂

Rectangulation of simple, chord-free polygons

We can divide orthogonal polygons into two classes: those that contain holes, and those that are hole-free.  Hole-free polygons are also called simple polygons, and we will limit ourselves to rectangulation of simple orthogonal polygons for the remainder of this post.

By convention, we assume the input size to our rectangulation problem is , the number of vertices of polygon .  Note that this means that a square with a huge interior is “smaller” than an L-shape with a small interior: complexity of the boundary is more important than a shape’s total area.  The justification for this is that a rectangulation algorithm is likely to receive a set of vertices as input, and we assume that each pair of vertex coordinates can be stored in some constant amount of memory, so the complexity of executing a rectangulation is identical for every polygon that is similar (in the Euclidean sense) to .

In an orthogonal polygon, there are two types of vertices: those at the point of a 90 degree interior angle (convex vertices), and those at the point of a 270 degree interior angle (concave vertices).  In many rectangulation algorithms, the number of concave vertices is a fundamental parameter; indeed, at the end of this post, we will change the input size to the number of concave vertices of , not the total number of vertices of .  At first, this may seem pointless, since the asymptotic complexity of the algorithm remains the same, regardless of the definition of , as there are exactly 4 fewer concave vertices than convex vertices in any orthogonal polygon.  To gain an intuition for why authors focus on concave vertices, we will build a rectangulation algorithm for any polygon from a rectangulation algorithm that assumes the concave vertices of have a niceness property.

Let and be concave vertices of that do not share the same edge of .  Call and cogrid if they lie on the same horizontal or vertical line.  A chord is a line segment fully contained in that connects two cogrid (concave) vertices.  The follolwing is a simple algorithm that finds a rectangulation for any that contains no chords.  I believe it appeared first in “Minimal Rectangular Partition of Digitized Blobs,” by Ferrari et al. — a paper whose title I love, but which I can only find behind paywalls, unfortunately.

Algorithm 1

1. Input: a simple orthogonal polygon with no chords.
2. For each concave vertex, select one of its incident edges.  (Two edges are incident to each concave vertex.)
3. Extend this edge until it hits another such extended edge, or a boundary edge of .
4. Return the extensions of edges as the rectangulation.

So, if has no chords, the number of segments we need to draw is exactly the number of concave vertices of .  We will now use this algorithm as a subroutine in a larger algorithm to rectangulate any simple .

Rectangulation of simple polygons with chords

Now let’s assume has 1 or more chords.  Let be the size of the largest set of nonintersecting chords, and let’s redefine to be the number of concave vertices (no longer just the number of vertices).  Ferrari et al. showed that the number of rectangles in a minimum-rectangle partition of is .  Here is their algorithm to achieve that.

Algorithm 2

1. Input a simple orthogonal polygon.
2. Find the chords of .
3. Construct a bipartite graph with edges between vertices in the sets and , where each vertex in corresponds to a vertical chord, and each vertex in corresponds to a horizontal chord.  Draw an edge between vertices and iff the chords corresponding to and intersect.
4. Find a maximum matching of the bipartite graph.
5. Use to find a maximum independent set of vertices of the bipartite graph.  (This set corresponds to a maximum set of nonintersecting chords of .)
6. Draw the chords corresponding to in .  This subdivides into smaller polygons, none of which contains a chord.
7. Using Algorithm 1, rectangulate each of the chordless polygons.
8. Output the union of the rectangulations of the previous step.

This algorithm is discussed in Graph-Theoretic Solutions to Computational Geometry Problems by David Eppstein, where he talks about work that was done to optimize the algorithm through a better maximum matching algorithm, and using a specialized geometric data structure.  Ferrari et al. used the Hopcroft/Karp maximum matching algorithm to obtain a rectangulation algorithm that runs in time .  Rather than go into more detail, I will now outline a method that yields a strictly better bound.

Rectangulation in time

Through a different method, Liou et al. demonstrated an algorithm with the property stated in the title of their article: Minimum Partitioning Simple Rectilinear Polygons in Time.  The algorithm is technical and lengthy; I will focus on a few points.

Liou et al. sidestep the (relatively) expensive step of building the bipartite graph in Algorithm 2.  The outline of their algorithm is:

Algorithm 3 (outline)

1. Input a simple orthogonal polygon.
2. Find a maximum matching of the chords of without constructing the bipartite graph, by taking advantage of the specialized geometry of those chords.  (This requires time.)
3. Given the maximum matching, find a set of maximum nonintersecting chords of .  (This step is essentially the same as before, and requires time.)
4. Use Algorithm 1 to partition each chord-free subpolygon obtained from the nonintersecting chords found in Step 3,  (Requires time.)

So Algorithm 3, overall, runs in time.

W.T. Liou, J.J.M. Tan, & R.C.T. Lee (1989). Minimum Partitioning Simple Rectilinear Polygons in O(n log log n) Time Symposium on Computational Geometry, 344-353 : 10.1145/73833.73871

FERRARI, L., SANKAR, P., & SKLANSKY, J. (1984). Minimal rectangular partitions of digitized blobs Computer Vision, Graphics, and Image Processing, 28 (1), 58-71 DOI: 10.1016/0734-189X(84)90139-7