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

Buchin  showed that under "reasonable" assumptions, (polynomial point spread) incremental construction of Delaunay triangulations using the biased randomized ordering of Amenta et al.  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