##
On Compatible Star Decompositions of Simple Polygons

We introduce the notion of compatible star decompositions
of simple polygons. In general,
given two polygons with a correspondence between their vertices,
two polygonal decompositions of the two polygons are said to be
* compatible * if there exists a one-to-one mapping between them
such that the corresponding pieces are defined by corresponding vertices.
For compatible * star * decompositions we
also require correspondence between star points of the star pieces.
Compatible star decompositions have applications in computer animation
and shape representation and analysis.

We present two algorithms for constructing compatible star decompositions
of two simple polygons.
The first algorithm is optimal in the number of pieces in the decomposition,
providing that such a decomposition exists without adding Steiner vertices.
The second algorithm constructs compatible star decompositions
with Steiner vertices, which are not
minimal in the number of pieces but are worst case optimal in this
number and in the number of added Steiner vertices.
We prove that some pairs of polygons require O(n^2) pieces, and that
the decompositions computed by the second algorithm possess no more than
O(n^2) pieces.

In addition to the contributions regarding compatible star decompositions,
the paper also corrects
an error in the only previously published polynomial algorithm for constructing
a minimal star decomposition of a simple polygon, an error which might lead to a
non-minimal decomposition.

* IEEE Transactions on Visualization and Computer Graphics*,
3(1):87-95, 1997.