Searching for open source implementation of medium dimension k-Voronoi tessellation. References that describe the data structures and algorithms would be appreciated.
An implementation exists that is not CGAL based and that is considered as very good by practitioners : see http://www.qhull.org/
I know that Professor Boissonnat (INRIA) has published an article about this topic:
"An efficient implementation of Delaunay triangulations in medium dimensions" with S. Hornus. It should be integrated in CGAL as soon as possible, I suppose.
Thanks, David., I have read and enjoyed Professor Boissonnat's paper and sent him a note to inquire about availability of the implementation. No reply, yet, but I am hopeful.
An implementation exists that is not CGAL based and that is considered as very good by practitioners : see http://www.qhull.org/
Thanks for your answer, Jean-François. I was unaware that qhull has any specific support for k-Delaunay or k-Voronoi, but have used some of its features in the past. I'll check it out!
In addition to the incisive observations already made by others in this thread, see
J.E. Lammersfeld, Implementing Four-Dimensional Triangulations in CGAL, M.Sc. thesis, University of Notre Dame, 2006:
http://etd.nd.edu/ETD-db/theses/available/etd-04102006-141513/unrestricted/LammersfeldJE042006T.pdf
Voronoi diagrams and Delaunay triangulations are introduced in ch. 1. A detailed introduction to CGAL triangulation implementation is given in ch. 4, starring on page 45.
- Badges
- Science method