INPUT OUTPUT

**Problem:**
What is the set of points within *P* which have more than
one closest point on the boundary of *P*?

**Excerpt from**
The Algorithm Design Manual:
The medial-axis transformation is useful in *thinning*
a polygon, or, as is sometimes said, finding its *skeleton*.
The goal is to extract a simple, robust representation of
the shape of the polygon.
As can be seen from the figures above, the thinned versions of the letters
capture the essence of the shape of an `A' and a `B', and would be relatively
unaffected by changing the thickness of strokes or by adding
font-dependent flourishes such as serifs.

The medial-axis transformation of a polygon is always a tree, making it fairly easy to use dynamic programming to measure the ``edit distance'' between the skeleton of a known model and the skeleton of an unknown object. Whenever the two skeletons are close enough, we can classify the unknown object as an instance of our model. This technique has proven useful in computer vision and in optical character recognition. The skeleton of a polygon with holes (like the `A' and `B') is not a tree, but an embedded planar graph, but it remains easy to work with.

Computational Geometry in C by Joseph O'Rourke | Discrete Voronoi Skeletons by R. Ogniewicz | Algorithms for Graphics and Image Processing by T. Pavlidis |

Pattern Classification and Scene Analysis by R. Duda and P. Hart |

This page last modified on 2008-07-10 . www.algorist.com