CGAL users discussion list

[Ben Haller <>]

  Hi!  I'm currently using CGAL's Delaunay_d to do d-dimensional 
triangulations, with some success.  I realize that CGAL does not provide a 
d-dimensional Voronoi package, but I'm hoping it is possible to extract just 
enough information from Delaunay_d to be able to do a computation I'd like to 
do.  Specifically, if vertices v1 and v2 are connected in the Delaunay 
triangulation, they have a (d-1)-dimensional Voronoi facet between them, and 
I would like to be able to find the centroid of that facet.  If I've got all 
this stuff straight in my head, the vertices of the facet are the centers of 
the hyperspheres bounding the simplices that contain both v1 and v2.  I can 
get the set of simplices that contain both v1 and v2 from Delaunay_d.  There 
seems to be no API available to get the bounding hypersphere of a simplex, 
unfortunately; I get the impression that the Delaunay_d object has that 
information, but it does not expose it in the API.  If I could get the 
hypersphere centers, then the centroid of a set of n-dimensional points is 
computed easily enough.  In a perfect world, I'd really like to get the 
centroids of *clipped* Voronoi facets, such that facets of infinite extent 
are clipped to the unit hypercube before the centroid is computed, but I 
haven't the slightest idea how I'd go about that.  That's really what I'd 
like, though, so that the infinite-extent facets don't blow up my algorithm; 
the centroid of the clipped facet is actually exactly what I want, for my 
application.

  Anyhow, my grasp of both d-dimensional geometry and the CGAL APIs is not 
really up to solving this problem, but I'm hoping somebody else on the list 
has already tackled it, or can point me in the right direction.  Thanks!

Ben Haller
McGill University