Beating the spread: time-optimal point meshing

We present NetMesh, a new algorithm that produces a conforming Delaunay mesh for point sets in any fixed dimension with guaranteed optimal mesh size and quality. Our comparison-based algorithm runs in O(n log n + m) time, where n is the input size and m is the output size, and with constants depending only on the dimension and the desired element quality. It can terminate early in O(n log n) time returning a O(n) size Voronoi diagram of a superset of P, which again matches the known lower bounds. The previous best results in the comparison model depended on the log of the spread of the input, the ratio of the largest to smallest pairwise distance. We reduce this dependence to O(log n) by using a sequence of ε-nets to determine input insertion order into a incremental Voronoi diagram. We generate a hierarchy of well-spaced meshes and use these to show that the complexity of the Voronoi diagram stays linear in the number of points throughout the construction.