# Curve Reconstruction

Applet By Amit Rosner

The following Java applet demonstrates how to construct a crust curve from some
scattered points in the plane.

The solution is simple, and involves two important concepts in computational geometry:
the Voronoi Diagram and the Delaunay Triangulation.

Definition: Let S be a finite set of points in the plane, and let V be the vertices of the
Voronoi diagram of S. An edge between points s1, s2 (both belong to S)
belongs to the crust of S if there is a disk, empty of points in the union
of S and V, touching s1 and s2.

Therefore, the  algorithm is simply as follows:

1) Let S and V be as stated above, and Let S' be the union of S and V.
2) Let D be the Delaunay triangulation of S'.
3) An edge of D belongs to the crust of S if both its endpoints belong to S.

Example:

Set of points                      Voronoi diagram                Delaunay triangulation
(the crust highlighted)

The applet extends an applet by Denis Constales that implements the triangulation
algorithm, that can be found at http://cage.rug.ac.be/~dc/alhtml/Delaunay.html.

Reference: paper by Nina Amenta, Marshall Bern and David Eppstein from 2.12.1997:
"The Crust and the Beta-Skeleton: Combinatorial Curve Reconstruction".