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 →

### Like this:

Like Loading...