2
$\begingroup$

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).
  2. Buchin, Kevin. "Constructing Delaunay triangulations along space-filling curves." Algorithms-ESA 2009. Springer Berlin Heidelberg, 2009. 119-130.
Improve this question
$\endgroup$
  • $\begingroup$ Does the order in which points are inserted by Fortune's sweep-line algorithm qualify or not? $\endgroup$ – Jeffε Feb 14 '14 at 22:51
  • $\begingroup$ 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. $\endgroup$ – Geoffrey Irving Feb 14 '14 at 22:52
  • $\begingroup$ Huh? Nothing happens "randomly" in Fortune's algorithm; it's deterministic. $\endgroup$ – Jeffε Feb 14 '14 at 22:57
  • $\begingroup$ 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. $\endgroup$ – Geoffrey Irving Feb 14 '14 at 23:00
  • $\begingroup$ 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 $\endgroup$ – Vicente Helano Feb 16 '14 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.