Curve Reconstruction

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