Tying up loose ends from my three posts in December about rectangulation of orthogonal polygons.
- Derrick Stolee requested in a comment a resolution of the computational complexity of the 3D version of the problem of decomposing a shape into the minimum number of rectangles. I found a reference that proves the problem is NP-complete, by directly reducing the problem to a variant of 3SAT. The diagrams of the gadgets used are pretty cool — the gadgets look like children’s toys used to build 3D structures. Rectangular partition is polynomial in two dimensions but NP-complete in three, by Victor J. Dielissen and Anne Kaldewaij, Information Processing Letters, April 1991.
- The survey Polygon Decomposition by J. Mark Keil (1996) has much more information on exact algorithms for rectangulation, triangulation, and problems I did not mention at all, like covering.
- There is an extensive literature on approximation algorithms for finding a minimum-length rectangulation of an orthogonal polygon with holes. (The problem is NP-complete even for the case where the polygon is a rectangle and its interior holes are points.) I can recommend the survey Minimum Edge-Length Rectangular Partitions, by Gonzalez and Zheng (in Handbook of Approximation Algorithms and Metaheuristics, 2007).
Victor J. Dielissen, & Anne Kaldewaij (1991). Rectangular partition is polynomial in two dimensions but NP-complete in three Information Processing Letters, 38 (1), 1-6 : 10.1016/0020-0190(91)90207-X
In this third (and final) post on polygon rectangulation, I will consider how to find the rectangulation of minimum total length for an orthogonal polygon. In part one of this short series, we considered rectangulations with a minimum number of rectangles; and, in part two, we considered rectangulations with a minimum number of “fat” rectangles. I’ve saved this post for last, because this may be the most useful rectangulation application in VLSI, and this is the rectangulation problem that Ming-Yang Kao and I have applied to self-assembly (though I won’t discuss our application in this post).
The minimum-length rectangulation algorithm appeared in Minimum Edge Length Partitioning of Rectilinear Polygons, by Lingas, Pinter, Rivest and Shamir (1982). The authors proved both a positive and a negative result. The positive result — which I will focus on today — is a dynamic programming algorithm that finds an optimal minimum-length rectangulation for any orthogonal polygon with no interior holes. The negative result is a proof that, if the input polygon is allowed to have holes, then the problem is NP-complete. (I discussed the proof of this result in a previous blog post.) Continue reading
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). Continue reading
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. :-) Continue reading
Figures 2 and 3 from Connected Guards in Orthogonal Art Galleries, by Pinciu (click to enlarge)
The Art Gallery Problem is one of the fundamental problems in computational geometry. It’s easy to state, easy to motivate, and “simple” variations of it can be very hard to solve. The problem: given a building, what is the fewest number of guards you need to station in order to guard every part of the building? Mathematically, we abstract this out: the floor plan of the building becomes a polygon, and the goal is to determine what is the fewest number of “guard points” I can place on the boundary or in the interior of the polygon, so that every point in the polygon can be connected via a line segment to the guard point, so the segment lies completely within the interior of the polygon.
More generally, this area of study is sometimes called “visibility problems,” and has found application in everything from computer graphics to robot motion. I recently read a paper by Val Pinciu, Connected Guards in Orthogonal Art Galleries, where he proves the following theorem.
Theorem: Let . An orthogonal polygon with sides can be completely guarded by a set of at most connected guards.
Pinciu’s proof is constructive — he finds an explicit guard set — and his core algorithm is brief enough to discuss in a blog post, so that’s what I’m going to do after the jump. Continue reading
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 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.