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).