TR92-06: A unified approach to orthogonal polygon covering problems via dent diagrams.

Joseph C. Culberson and Robert A. Reckhow.

Date: February 1989.

University of Alberta Computing Science Technical Report TR89-06

Abstract

Culberson and Reckhow introduced the concept of a dent diagram to formalize the problem of covering certain subclasses of orthogonal polygons by orthogonally convex polygons. In this paper we apply similar ideas to define dent diagrams for two pairs of problems:
  1. covering orthogonal polygons with rectangles and with orthogonal stars, and
  2. covering orthogonal polygons with orthogonally convex polygons and with a version of orthogonal star-like polygons.
In both cases, we subdivide the given polygon into regions, based on the appropriate notion of visibility, and show that these regions must be the constituents of the polygons in a minimal covering. We also identify certain regions called ``sources'', that play a special role when covering by convex components, and other regions called ``sinks'', that play an analogous role when the covering components are stars. Our formalism reveals strong parallels among the two pairs of problems, and points out the close interrelationship between convex and star covers. Using the insight provided by this formalism, we derive efficient new algorithms for covering two different classes of orthogonal polygons with monotone orthogonal stars. It is hoped that this new insight will lead to improved algorithms or NP-completeness results for these covering problems. We also indicate what would be required to extend our methods to the general (non-orthogonal) case, and conjecture that such an extension might not be possible.

Queries: email joe@cs.ualberta.ca

Joseph Culberson