Covering a simple orthogonal polygon with a minimum number of orthogonally convex polygons.

Joseph Culberson and Robert A. Reckhow

In Proceedings of the Third Annual Symposium on Computational Geometry, pages 268-277, June 1987.


The problem of covering a polygon with convex polygons has proven to be very difficult, even when restricted to the class of orthogonal polygons using orthogonally convex covers. We develop a method of analysis based on dent diagrams for orthogonal polygons and are able to show that Keil's O(n^2) algorithm for covering horizontally convex polygons is asymptotically optimal, but it can be improved to O(n) for counting the number of polygons required for a minimal cover. We also give an optimal O(n^2) covering algorithm and an O(n) counting algorithm for another subclass of orthogonal polygons. Finally, we develop a method of signatures which can be use to obtain polynomial time algorithms for an even larger class of orthogonal polygons.

The full version of this paper appears in Journal of Computer and System Sciences, vol 39(2), 166-204, October 1989.