flâneur

Polygon rectangulation, part 1: Minimum number of rectangles | Nanoexplanations

nanoexplanations.wordpress.com · 1,847 words · saved by 1 readers

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

Polygon rectangulation, part 1: Minimum number of rectangles | Nanoexplanations Nanoexplanations the blog of Aaron Sterling Skip to content Home About In memoriam: Yitzchak Dumiel The TCS of Chemoinformatics ← Can we derandomize BP.PP? Polygon rectangulation, part 2: Minimum number of fat rectangles → Polygon rectangulation, part 1: Minimum number of rectangles Posted on December 2, 2011 | 3 Comments 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, no

related reading