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