CS 269S, Fall 2010: Theory Seminar
CS Building, Room 243
3 Dec 2010:

Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent

Maarten Löffler

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 EMST in linear time. With the EMST at hand, we can find the Delaunay triangulation in linear time.

(Joint work with Wolfgang Mulzer, to appear at SODA 2011.)