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