| A survey of existing Voronoi/Delaunay meshes is presented, and a new algorithm for creating a 2D constrained Delaunay triangulation of points within a region or set of regions is given. The method uses a background grid to localize Delaunay neighbor searches, and works in O(k{dollar}sp2{dollar}nlogn) time where n is the number of points and k is proportional to the ratio of the highest to lowest point density within a given region. The method uses only information local to a point to determine connections and can be done independently for each point, thus making it suitable for parallel computers and large numbers of points. The algorithm can be implemented to use only O(k) main memory (independent of n), allowing the creation of large meshes on computers with limited memory. Source code and proofs that the method produces the full constrained Delaunay mesh are given. |
