Skip to main content
![Creative Commons 'BY' version 4.0 license]()
Orthogonal Dissection into Few Rectangles
Published Web Location
https://doi.org/10.1007/s00454-023-00614-wNo data is associated with this publication.
Abstract
We describe a polynomial time algorithm that takes as input a polygon with axis-parallel sides but irrational vertex coordinates, and outputs a set of as few rectangles as possible into which it can be dissected by axis-parallel cuts and translations. The number of rectangles is the rank of the Dehn invariant of the polygon. The same method can also be used to dissect an axis-parallel polygon into a simple polygon with the minimum possible number of edges. When rotations or reflections are allowed, we can approximate the minimum number of rectangles to within a factor of two.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.