


#include <LEDA/plane_alg.h>
#include <LEDA/map.h>


void CRUST(list<point> L, GRAPH<point,int>& G) 
{
  map<point,bool>     delaunay_point(false);
  GRAPH<circle,point> VD;

  // compute voronoi diagram VD

  VORONOI(L,VD);

  // mark delaunay points and append them to L

  node v;
  forall_nodes(v,VD)
  { if (VD.outdeg(v) < 2) continue; 
    point p = VD[v].center();
    delaunay_point[p] = true;
    L.append(p);
   }

  // compute delaunay triangulation G

  DELAUNAY_TRIANG(L,G);

  // and remove all voronoi points from G

  list<node> vlist;
  forall_nodes(v,G)
     if (delaunay_point[G[v]]) vlist.append(v);

  G.del_nodes(vlist);
   
}
