id: 06111131
dt: j
an: 06111131
au: Löffler, Maarten; Mulzer, Wolfgang
ti: Triangulating the square and squaring the triangle: quadtrees and Delaunay
    triangulations are equivalent.
so: SIAM J. Comput. 41, No. 4, 941-974 (2012).
py: 2012
pu: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
la: EN
cc: 
ut: well-separated pair decomposition; Delaunay triangulation; quadtree
ci: 
li: doi:10.1137/110825698
ab: Summary: We show that Delaunay triangulations and compressed quadtrees are
    equivalent structures. More precisely, we give two algorithms: the
    first computes a compressed quadtree for a planar point set, given the
    Delaunay triangulation; the second finds the Delaunay triangulation,
    given a compressed quadtree. Both algorithms run in deterministic
    linear time on a pointer machine. Our work builds on and extends
    previous results by Krznaric and Levcopolous and Buchin and Mulzer. Our
    main tool for the second algorithm is the well-separated pair
    decomposition (WSPD), a structure that has been used previously to find
    Euclidean minimum spanning trees in higher dimensions. We show that
    knowing the WSPD (and a quadtree) suffices to compute a planar
    Euclidean minimum spanning tree (EMST) in linear time. With the EMST at
    hand, we can find the Delaunay triangulation in linear time. As a
    corollary, we obtain deterministic versions of many previous algorithms
    related to Delaunay triangulations, such as splitting planar Delaunay
    triangulations, preprocessing imprecise points for faster Delaunay
    computation, and transdichotomous Delaunay triangulations.
rv: