A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs Gary L. Miller Donald Sheehy Ameya Velingker 10.1184/R1/6587378.v1 https://kilthub.cmu.edu/articles/journal_contribution/A_Fast_Algorithm_for_Well-Spaced_Points_and_Approximate_Delaunay_Graphs/6587378 <p>We present a new algorithm that produces a well-spaced superset of points conforming to a given input set in any dimension with guaranteed optimal output size. We also provide an approximate Delaunay graph on the output points. Our algorithm runs in expected time O(2<sup>O(d)</sup>(n log n + m)), where n is the input size, m is the output point set size, and d is the ambient dimension. The constants only depend on the desired element quality bounds.</p> <p>To gain this new efficiency, the algorithm approximately maintains the Voronoi diagram of the current set of points by storing a superset of the Delaunay neighbors of each point. By retaining quality of the Voronoi diagram and avoiding the storage of the full Voronoi diagram, a simple exponential dependence on d is obtained in the running time. Thus, if one only wants the approximate neighbors structure of a refined Delaunay mesh conforming to a set of input points, the algorithm will return a size 2<sup>O(d)</sup>m graph in 2<sup>O(d)</sup>(n log n + m) expected time. If m is superlinear in n, then we can produce a hierarchically well-spaced superset of size 2<sup>O(d)</sup>n in 2<sup>O(d)</sup>n log n expected time.</p> 1977-01-01 00:00:00 computer sciences