Home | Bookmarks | Papers | Blog |

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__:

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".