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.
Abstract
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.
joe@cs.ualberta.ca