Skip to main content
3 of 3
Image link broken; now fixed.
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

An exact partition into the minimum number of rectangles can be found in $O(n^{3/2} \log n)$ time, if the set $S$ forms a region with $n$ corners. See David Eppstein's survey, "Graph-Theoretic Solutions to Computational Geometry Problems," arXiv:0908.3916. For primary references, see his answer to the earlier MO question, "split polygon into minimum amount of rectangles and triangles."


         ![Rectangle Partition][3]

Because there is a fast exact algorithm, perhaps there has not been study of approximation algorithms.

Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958