Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
The Structure Of Optimal Partitions Of Orthogonal Polygons Into Fat Rectangles, Joseph O'Rourke, Geetika Tewari
The Structure Of Optimal Partitions Of Orthogonal Polygons Into Fat Rectangles, Joseph O'Rourke, Geetika Tewari
Computer Science: Faculty Publications
Motivated by a VLSI masking problem, we explore partitions of an orthogonal polygon of n vertices into isothetic rectangles that maximize the shortest rectangle side over all rectangles. Thus no rectangle is "thin"; all rectangles are "fat". We show that such partitions have a rich structure, more complex than what one might at first expect. For example, for partitions all "cuts" of which are anchored on the boundary, sometimes cuts are needed 1/2 or 1/3 of the distance between two polygon edges, but they are never needed at fractions with a larger denominator. Partitions using cuts without any restrictions seem …