0

I am looking for stand-alone code to build the Delaunay triangulation of a set of 2D points. (No constraint, Euclidean metric.) In fact I need it to build a Euclidean Minimum Spanning Tree, so that a direct implementation can do as well.

I have two requirements:

  • should correctly handle aligned and cocircular points correctly (the coordinates are small integers, 64 bits arithmetic will be exact);

  • should be time-efficient, O(N Log N) (such as Fortune's sweepline or Lee & Schachter divide & conquer).

The language is preferably C or C++ but I can translate from others. (I prefer a lightweight solution to a full-fledged package such as CGAL.)

Improve this question
4
  • did you have a look at metis (glaros.dtc.umn.edu/gkhome/metis/metis/overview)? – albert May 17 '18 at 9:56
  • @albert: it doesn't address Delaunay/Voronoi, nor even ordinary MST's, does it ? – Yves Daoust May 17 '18 at 10:01
  • Not sure about it. Please mention your requirements regarding Voronoi combination Delaunay/Voronoi i the question. – albert May 17 '18 at 10:08
  • @albert: I need an EMST solution, which I am ready to implement myself from a Delaunay triangulation. This is said in the question. – Yves Daoust May 17 '18 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.