# Worst-case optimal Delaunay algorithm based on spatial sort and walking?

Buchin [2] showed that under "reasonable" assumptions, (polynomial point spread) incremental construction of Delaunay triangulations using the biased randomized ordering of Amenta et al. [1] with a space filling curve takes $O(n \log n)$ even when points are located by walking from the last inserted point. This reduces to $O(n)$ for uniformly random points if the BRIO jumps are treated carefully.

Question: Are there any "simple to compute" orders which are worst case $O(n \log n)$ for all general position inputs? I am leaving "simple" intentionally vague, but roughly I mean simpler than computing the Delaunay triangulation itself (from which an optimal order is easy to derive).

• Does the order in which points are inserted by Fortune's sweep-line algorithm qualify or not? – Jeffε Feb 14 '14 at 22:51
• The sweep line insertion order is both as hard to compute as Delaunay and doesn't give $O(n \log n)$ since it jumps randomly around along the sweep line, so no. – Geoffrey Irving Feb 14 '14 at 22:52
• Huh? Nothing happens "randomly" in Fortune's algorithm; it's deterministic. – Jeffε Feb 14 '14 at 22:57
• Sorry, "wildly" is a better term than "randomly." In any case, the distance through the triangulation between neighboring points would be $\sqrt{n}$ even for well distributed points, resulting in an $O(n^{1.5})$ algorithm. – Geoffrey Irving Feb 14 '14 at 23:00
• I don't know a simple order theoretically, but there is an strategy that works very well in practice implemented in CGAL: doc.cgal.org/latest/Spatial_sorting/index.html – Vicente Helano Feb 16 '14 at 0:40