Orthogonally Convex Coverings of Orthogonal Polygons without Holes
Joseph Culberson and Robert A. Reckhow
Journal of Computer and System Sciences Vol. 39, No. 2:166-204, 1989.
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.
joe@cs.ualberta.ca