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.


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.