Incremental construction along space-filling curves.
Kevin Buchin · 2005
For the incremental construction of a Delaunay triangulation, we prove that inserting points in rounds and walking along a space-filling curve in each round yields an algorithm running in linear expected time for uniformly distributed points. We complement this result by a simpler incremental construction running in linear expected time in any dimension. 1