TY - GEN
T1 - Constructing Delaunay triangulations along space-filling curves
AU - Buchin, K.
PY - 2009
Y1 - 2009
N2 - Incremental construction con BRIO using a space-filling curve order for insertion is a popular algorithm for constructing Delaunay triangulations. So far, it has only been analyzed for the case that a worst-case optimal point location data structure is used which is often avoided in implementations. In this paper, we analyze its running time for the more typical case that points are located by walking. We show that in the worst-case the algorithm needs quadratic time, but that this can only happen in degenerate cases. We show that the algorithm runs in O(n logn) time under realistic assumptions. Furthermore, we show that it runs in expected linear time for many random point distributions.
This research was supported by the Deutsche Forschungsgemeinschaft within the European graduate program ’Combinatorics, Geometry, and Computation’ (No. GRK 588/2) and by the Netherlands’ Organisation for Scientific Research (NWO) under BRICKS/FOCUS grant number 642.065.503 and project no. 639.022.707.
AB - Incremental construction con BRIO using a space-filling curve order for insertion is a popular algorithm for constructing Delaunay triangulations. So far, it has only been analyzed for the case that a worst-case optimal point location data structure is used which is often avoided in implementations. In this paper, we analyze its running time for the more typical case that points are located by walking. We show that in the worst-case the algorithm needs quadratic time, but that this can only happen in degenerate cases. We show that the algorithm runs in O(n logn) time under realistic assumptions. Furthermore, we show that it runs in expected linear time for many random point distributions.
This research was supported by the Deutsche Forschungsgemeinschaft within the European graduate program ’Combinatorics, Geometry, and Computation’ (No. GRK 588/2) and by the Netherlands’ Organisation for Scientific Research (NWO) under BRICKS/FOCUS grant number 642.065.503 and project no. 639.022.707.
U2 - 10.1007/978-3-642-04128-0_11
DO - 10.1007/978-3-642-04128-0_11
M3 - Conference contribution
SN - 978-3-642-04127-3
T3 - Lecture Notes in Computer Science
SP - 119
EP - 130
BT - Algorithms - ESA 2009 (17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings)
A2 - Fiat, A.
A2 - Sanders, P.
PB - Springer
CY - Berlin
ER -