Orthogonally convex coverings of orthogonal polygons without holes

摘要

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(n2) 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(n2) covering algoring and an O(n) counting algorithm for another subclass of orthogonal polygons. Finally, we develop a method of signatures which can be used to obtain polynomial time algorithms for an even larger class of orthogonal polygons.