This post is the second in a series on polygon rectangulation. In my previous post, I discussed methods to decompose an orthogonal polygon into a minimum number of rectangles. (See that post for definitions and motivation.) In my next post, I will consider finding a rectangulation of a minimum length — a topic very important in VLSI. In this post, I will consider a modification to the minimum-number-of-rectangles problem; the modification was motivated by concerns in VLSI, but, as yet, only a theoretical algorithm exists, with a running time of . (That is not a typo, and it is obtained through a “natural” dynamic programming solution to the problem I am about to state.)
Printed circuits are created through a process called photolithography, in which electron beams etch a design onto a substrate. While these electron beams are, in one sense, extremely narrow, as the Wikipedia article on VLSI states, current photolithography techniques “tend closer to the fundamental laws of optics.” Among other things, this means that the fixed minimum width of an electron beam is suddenly important. In principle, it implies a “fat fingers” problem. Suppose our substrate is in the shape of orthogonal polygon , and we use a rectangulation technique from the previous post to rectangulate . We may not be able to apply the rectangulation in real life, because we have no guarantee that all of the rectangles are wider than our electron beam. Therefore, we would like to constrain the space of rectangulations we consider to ones that are feasible to etch — informally, ones that contain only “fat” rectangles. We formalize this optimization problem as follows.
Fat Rectangle Optimization Problem: Given an orthogonal polygon , maximize the shortest side over all rectangulations of . Among the partitions with the same , choose the partition with the fewest number of rectangles.
This optimization problem has been studied by O’Rourke and co-authors in at least three papers. In this blog post, I will focus on consideration of The Structure of Optimal Partitions of Orthogonal Polygons into Fat Rectangles, by O’Rourke and Tewari (2004).
Rectangulations limited to vertex cuts
We saw in the last post that to obtain a minimum-rectangle rectangulation, we could limit ourselves to considering rectangulations whose line segments were boundary edges of , or rooted at convex vertices of . Given , we can define its vertex grid, by drawing horizontal and vertical lines through each vertex of , and a point is a member of the vertex grid iff it is located on the intersection of two of those lines. We will see in the next post that, to obtain a minimum-length rectangulation, we can limit consideration to line segments between points that lie on the vertex grid. Neither of these restrictions is sufficient for the Fat Rectangle Optimization Problem, as the figure below demonstrates.
This is Figure 4 in the O’Rourke and Tewari paper. If we try to move (or redraw) the segments so they are rooted at vertices, or at points on the vertex grid, we necessarily produce a rectangle that is skinnier than any in the figure. Moreover, there is a segment that is floating, i.e., not anchored to the boundary at either endpoint.
For the rest of this post, we will call a non-boundary segment of a rectangulation a cut. The terminology is motivated by photolithography: those are the segments we would need to cut into the substrate. One way to simplify this problem is to limit the types of cuts we permit to appear in rectangulations. Let us call a vertex cut a cut with at least one endpoint a polygon vertex.
As long ago as 2001, O’Rourke, Pashchenko and Tewari designed an algorithm to solve Fat Rectangle Optimization limited to vertex cuts, and they implemented their algorithm (postscript file of CCCG abstract). They noted empirically that the algorithm appeared to perform at with inputs of random orthogonal polygons. Their algorithm was inspired by the Liou et al. algorithm for polygon rectangulation that I outlined in my previous post.
As an aside, the notion of a “random orthogonal polygon” is surprisingly nontrivial. One paper that provides methods for this is Generating Random Orthogonal Polygons, by Tomás and Bajuelos. No polynomial time algorithm is known for the problem of uniformly randomly generating polygons with a given set of vertices, so researchers must use heuristics, or limit the types of polygons they generate. Further, Tomás and Bajuelos base (some of) their work on a computer program supplied by O’Rourke that is originally based on methods from a 1991 technical report by O’Rourke and Virmani in which the authors state, “A precise definition of what constitutes a random polygon seems elusive, and no attempt will be made here to clarify this notion.” I have no additional wisdom to impart, but I thought you might want to know that there is something important (or at least ill-defined) hiding just under the surface here.
Rectangulations limited to anchored cuts
An anchored cut is a cut that is not a floating cut; in other words, at least one endpoint of an anchored cut is on the boundary of the polygon. The figure above shows that there exist polygons for which anchored cuts do not suffice to find the optimal solution of the Fat Rectangle Optimization Problem. There is a nice structure on solutions obtainable from anchored cuts, but O’Rourke and Tewari initially found it surprising. Their motivating example for their proof was this figure (which is Figure 8 in the paper).
The surprising aspect of this is that the vertical anchored cuts do not lie midway between any pair of vertices, but rather lie 1/3 and 2/3 of the distance between vertices 3 and 11. It turns out that this phenomenon can be captured in a theorem, which is Theorem 6 of O’Rourke and Tewari.
Theorem: There exists an optimal anchored partition of a polygon such that every movable anchored cut has coordinate or , where and are (either x or y) coordinates of two vertices of .
This means that one can define a grid of possible anchor points from the vertices of , and then evaluate rectangulations based on “vertex cuts” anchored at that grid of possible anchor points, using the already-existing vertex-cut algorithm mentioned in the previous section. Since there are possible anchor points, this then gives a algorithm for the Fat Rectangle Optimization Problem limited to anchored cuts.
Rectangulations with no restriction on types of cut
Analysis of rectangulations based on unrestricted cuts makes up about half of O’Rourke and Tewari’s paper. They prove many interesting combinatorial and geometric facts about fat rectangulations, but, as they put it at the end of one lemma, “There is an overestimation at several points in the above argument; we do not believe the quoted upper bounds can be achieved. It would be of interest to establish tight bounds.” So they end up proving that a solution to the Fat Rectangle Optimization Problem lies, in principle, in polynomial time — but the exponent is one of the largest ones I have seen to come out of a “natural” argument. (For other algorithms that “naturally” produce large exponents and/or large constants, see this CSTheory question.)
Where does the exponent 42 come from? This is just mentioned briefly in the “Structure” paper, but is explained in detail in Partitioning Orthogonal Polynomials into Fat Rectangles in Polynomial Time by O’Rourke and Tewari (2002). The authors obtain combinatorial bounds on the maximum number of rectangles in an optimal partition (), on the total number of cuts required (), and on the amount of nesting of floating cuts inside floating rectangles that might occur in worst case (depth ). Bounds like this allow them to prove the following theorem.
Theorem: There is an optimal partition whose cuts fall on a subset of gridlines.
This can be considered an analogue to the fact that finding a minimum-length rectangulation can be done by considering only cuts anchored to the polygon’s vertex grid, as I mentioned at the beginning of the post. Unfortunately, lines instead of points means that a dynamic programming algorithm needs a much larger table of subproblems to consider.
There are, of course pairs of vertices of the input polygon . One combinatorial bound the authors prove is that any set of cuts between two vertices which is “good” — that is, which may be considered an optimal solution to a subproblem, and available for solution to a larger problem — is at most distance 4 away from a chain of cuts that has chain length at most 10. It then requires time and space to build this table of subproblem solutions, for use in a dynamic programming algorithm to solve the Fat Rectangle Optimization Problem without restrictions.
O’Rourke, J., & Tewari, G. (2004). The structure of optimal partitions of orthogonal polygons into fat rectangles Computational Geometry, 28 (1), 49-71 DOI: 10.1016/j.comgeo.2004.01.007
J. O’Rourke, & G. Tewari (2002). Partitioning orthogonal polygons into fat rectangles in polynomial time Canadian Conference on Computational Geometry, 97-100