{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:09Z","timestamp":1787337549114,"version":"build-2736575974"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/110825698","type":"journal-article","created":{"date-parts":[[2012,8,23]],"date-time":"2012-08-23T15:28:21Z","timestamp":1345735701000},"page":"941-974","source":"Crossref","is-referenced-by-count":6,"title":["Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent"],"prefix":"10.1137","volume":"41","author":[{"given":"Maarten","family":"L\u00f6ffler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,8,23]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574698"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/090766437"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"M. \\SortNoopBergde Berg, O. Cheong, M. van Kreveld, and M. Overmars,\n                      Computational Geometry: Algorithms and Applications\n                      , 3rd ed., Springer-Verlag, Berlin, 2008.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80059-5"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000303"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"J.D. Boissonnat and M. Yvinec,\n                      Algorithmic Geometry\n                      , Cambridge University Press, Cambridge, UK, 1998.","DOI":"10.1017\/CBO9781139172998"},{"key":"atypb7","first-page":"37","volume":"3","author":"O.","year":"1926","journal-title":"Pr\u00e1ce Moravsk\u00e9 Pr\u0306\u00edrodov\u0115deck\u00e9 Spolec\u0306nosti"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9430-0"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944347"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/070693217"},{"key":"atypb11","first-page":"291","author":"Callahan P. B.","year":"1993","journal-title":"Philadelphia"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.02.008"},{"key":"atypb14","unstructured":"T. M. Chan and M. P\u01cetra\u015fcu,\n                      Transdichotomous results in computational geometry,II:Offline search\n                      , preprint, arXiv:1010.1948, 2010."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/07068669X"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355562"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0939-8"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9346-8"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795285916"},{"key":"atypb21","first-page":"226","author":"Clarkson K. L.","year":"1983","journal-title":"NJ"},{"key":"atypb22","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,\n                      Introduction to Algorithms\n                      , 3rd ed., MIT Press, Cambridge, MA, 2009."},{"key":"atypb23","first-page":"168","author":"Das G.","year":"1989","journal-title":"Berlin"},{"key":"atypb24","first-page":"793","volume":"7","author":"Delaunay B.","year":"1934","journal-title":"Izv. Akad. Nauk SSSR Otdel. Mat. Estestvennyh Nauk"},{"key":"atypb25","first-page":"30","volume":"2","author":"Devillers O.","year":"2011","journal-title":"J. Comput. Geom."},{"key":"atypb26","first-page":"425","author":"Eppstein D.","year":"2000","journal-title":"Amsterdam"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195908002568"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80064-9"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90062-5"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.09.001"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"S. Har-Peled,\n                      Geometric Approximation Algorithms\n                      , Math. Surveys Monogr. 173, AMS, Providence, RI, 2011.","DOI":"10.1090\/surv\/173"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187821"},{"key":"atypb36","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming: Fundamental Algorithms\n                      , Vol. 1, 3rd ed., Addison-Wesley, Reading, MA, 1997."},{"key":"atypb37","first-page":"443","author":"Krznaric D.","year":"1995","journal-title":"Berlin"},{"key":"atypb38","first-page":"1","volume":"5","author":"Krznaric D.","year":"1998","journal-title":"Nordic J. Comput."},{"key":"atypb39","first-page":"446","volume":"6","author":"Krznaric D.","year":"1999","journal-title":"Nordic J. Comput."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.12.007"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek,\n                      Lectures on Discrete Geometry\n                      , Springer-Verlag, New York, 2002.","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"atypb42","first-page":"424","author":"Musin O.","year":"1997","journal-title":"New York"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and M. I. Shamos,\n                      Computational Geometry. An Introduction\n                      , Springer-Verlag, New York, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"atypb44","first-page":"199","author":"Pyrga E.","year":"2008","journal-title":"New York"},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"H. Samet,\n                      The Design and Analysis of Spatial Data Structures\n                      , Addison-Wesley, Boston, 1990. \u00f8nelongpage","DOI":"10.1007\/3-540-52208-5_28"},{"key":"atypb46","first-page":"520","author":"Sch\u00f6nhage A.","year":"1979","journal-title":"Berlin"},{"key":"atypb47","first-page":"151","author":"Shamos M. I.","year":"1975","journal-title":"NJ"},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan,\n                      Data Structures and Network Algorithms\n                      , CBMS-NSF Reg. Conf. Ser. Appl. Math. 44, SIAM, Philadelphia, 1983.","DOI":"10.1137\/1.9781611970265"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1137\/0217035"},{"key":"atypb50","first-page":"320","author":"Varadarajan K. R.","year":"1998","journal-title":"NJ"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/0211059"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110825698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:16:39Z","timestamp":1787336199000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110825698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/110825698"],"URL":"https:\/\/doi.org\/10.1137\/110825698","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}