<p>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.</p>

<p><strong>Question</strong>: 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).</p>

<ol>
<li><a href="http://www.inf.fu-berlin.de/groups/ag-ti/teaching/WiSe2000/uploads/tx_tipublications/Incremental_constructions_con_BRIO_02.pdf" rel="nofollow">Amenta, Nina, Sunghee Choi, and Günter Rote. "Incremental Constructions con BRIO." (2003).</a></li>
<li><a href="http://link.springer.com/chapter/10.1007%2F978-3-642-04128-0_11" rel="nofollow">Buchin, Kevin. "Constructing Delaunay triangulations along space-filling curves." Algorithms-ESA 2009. Springer Berlin Heidelberg, 2009. 119-130.</a></li>
</ol>

CC BY-SA 3.0
2014-02-14T22:51:05.773Z
Does the order in which points are inserted by Fortune's sweep-line algorithm qualify or not?
Jeffε
CC BY-SA 3.0
2014-02-14T22:52:13.533Z
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
CC BY-SA 3.0
2014-02-14T22:57:10.713Z
Huh? Nothing happens "randomly" in Fortune's algorithm; it's deterministic.
Jeffε
CC BY-SA 3.0
2014-02-14T23:00:18.830Z
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
<delaunay-triangulation><computational-geometry>
Worst-case optimal Delaunay algorithm based on spatial sort and walking?
Geoffrey Irving
# Worst-case optimal Delaunay algorithm based on spatial sort and walking?

(Asked by: username_0 on 2014-02-14)

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

1. [Amenta, Nina, Sunghee Choi, and Günter Rote. "Incremental Constructions con BRIO." (2003).](http://www.inf.fu-berlin.de/groups/ag-ti/teaching/WiSe2000/uploads/tx_tipublications/Incremental_constructions_con_BRIO_02.pdf)
2. [Buchin, Kevin. "Constructing Delaunay triangulations along space-filling curves." Algorithms-ESA 2009. Springer Berlin Heidelberg, 2009. 119-130.](http://link.springer.com/chapter/10.1007%2F978-3-642-04128-0_11)

**Tags:** delaunay-triangulation, computational-geometry
> **Comments:**
> **username_1**: Does the order in which points are inserted by Fortune's sweep-line algorithm qualify or not?  
> **username_0**: 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.  
> **username_1**: Huh? Nothing happens "randomly" in Fortune's algorithm; it's deterministic.  
> **username_0**: 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.  

---

## 0 answers

