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:
- covering orthogonal polygons with rectangles and with orthogonal
stars, and
- 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