{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:22:41Z","timestamp":1760368961851,"version":"3.41.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,4,1]],"date-time":"2011-04-01T00:00:00Z","timestamp":1301616000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"FOCUS\/BRICKS","award":["642.065.503639.022.707"],"award-info":[{"award-number":["642.065.503639.022.707"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,4]]},"abstract":"<jats:p>\n            We present several results about Delaunay triangulations (DTs) and convex hulls in transdichotomous and hereditary settings: (i) the DT of a planar point set can be computed in expected time\n            <jats:italic>O<\/jats:italic>\n            (sort(\n            <jats:italic>n<\/jats:italic>\n            )) on a word RAM, where sort(\n            <jats:italic>n<\/jats:italic>\n            ) is the time to sort\n            <jats:italic>n<\/jats:italic>\n            numbers. We assume that the word RAM supports the\n            <jats:italic>shuffle<\/jats:italic>\n            operation in constant time; (ii) if we know the ordering of a planar point set in\n            <jats:italic>x<\/jats:italic>\n            - and in\n            <jats:italic>y<\/jats:italic>\n            -direction, its DT can be found by a randomized algebraic computation tree of expected\n            <jats:italic>linear<\/jats:italic>\n            depth; (iii) given a universe\n            <jats:italic>U<\/jats:italic>\n            of points in the plane, we construct a data structure\n            <jats:italic>D<\/jats:italic>\n            for\n            <jats:italic>Delaunay queries<\/jats:italic>\n            : for any\n            <jats:italic>P<\/jats:italic>\n            \u2286\n            <jats:italic>U<\/jats:italic>\n            ,\n            <jats:italic>D<\/jats:italic>\n            can find the DT of\n            <jats:italic>P<\/jats:italic>\n            in expected time\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>P<\/jats:italic>\n            | log log |\n            <jats:italic>U<\/jats:italic>\n            |); (iv) given a universe\n            <jats:italic>U<\/jats:italic>\n            of points in 3-space in general convex position, there is a data structure\n            <jats:italic>D<\/jats:italic>\n            for\n            <jats:italic>convex hull queries<\/jats:italic>\n            : for any\n            <jats:italic>P<\/jats:italic>\n            \u2286\n            <jats:italic>U<\/jats:italic>\n            ,\n            <jats:italic>D<\/jats:italic>\n            can find the convex hull of\n            <jats:italic>P<\/jats:italic>\n            in expected time\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>P<\/jats:italic>\n            | (log log |\n            <jats:italic>U<\/jats:italic>\n            |)\n            <jats:sup>2<\/jats:sup>\n            ); (v) given a convex polytope in 3-space with\n            <jats:italic>n<\/jats:italic>\n            vertices which are colored with \u03c7 \u2265 2 colors, we can split it into the convex hulls of the individual color classes in expected time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            (log log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>2<\/jats:sup>\n            ).\n          <\/jats:p>\n          <jats:p>\n            The results (i)--(iii) generalize to higher dimensions, where the expected running time now also depends on the complexity of the resulting DT. We need a wide range of techniques. Most prominently, we describe a reduction from DTs to nearest-neighbor graphs that relies on a new variant of randomized incremental constructions using\n            <jats:italic>dependent<\/jats:italic>\n            sampling.\n          <\/jats:p>","DOI":"10.1145\/1944345.1944347","type":"journal-article","created":{"date-parts":[[2011,4,12]],"date-time":"2011-04-12T12:03:38Z","timestamp":1302609818000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Delaunay triangulations in\n            <i>O<\/i>\n            (sort(\n            <i>n<\/i>\n            )) time and more"],"prefix":"10.1145","volume":"58","author":[{"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[{"name":"TU Eindhoven, The Netherlands"}]},{"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[{"name":"Freie Universit\u00e4t Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2011,4,11]]},"reference":[{"unstructured":"Aggarwal A. 1988. Lecture notes in computational geometry. Tech. rep. 3 MIT Research Seminar Series MIT\/LCS\/RSS.  Aggarwal A. 1988. Lecture notes in computational geometry. Tech. rep. 3 MIT Research Seminar Series MIT\/LCS\/RSS.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1137\/090766437"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1006\/inco.1997.2632"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM-SIAM, 1106--1113","author":"Amenta N.","key":"e_1_2_1_4_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/777792.777824"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1007\/s00453-001-0013-y"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1006\/jcss.1998.1580"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1017\/CBO9780511804090"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.5555\/3116669.3117103"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1468075.1468121"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/800061.808735"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/355921.355927"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1016\/S0022-0000(05)80059-5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1142\/S0218195999000303"},{"doi-asserted-by":"crossref","unstructured":"Boissonnat J.-D. and Yvinec M. 1998. Algorithmic Geometry. Cambridge University Press Cambridge UK.   Boissonnat J.-D. and Yvinec M. 1998. Algorithmic Geometry. Cambridge University Press Cambridge UK.","key":"e_1_2_1_15_1","DOI":"10.1017\/CBO9781139172998"},{"unstructured":"Buchin K. 2007. Organizing point sets: Space-filling curves Delaunay tessellations of random point sets and flow complexes. Ph.D. dissertation Free University Berlin. http:\/\/www.diss.fu-berlin.de\/diss\/receive\/FUDISS_thesis_000000003494.  Buchin K. 2007. Organizing point sets: Space-filling curves Delaunay tessellations of random point sets and flow complexes. Ph.D. dissertation Free University Berlin. http:\/\/www.diss.fu-berlin.de\/diss\/receive\/FUDISS_thesis_000000003494.","key":"e_1_2_1_16_1"},{"unstructured":"Buchin K. 2008. Delaunay triangulations in linear time&amp;quest; (part I). arXiv:0812.0387.  Buchin K. 2008. Delaunay triangulations in linear time&amp;quest; (part I). arXiv:0812.0387.","key":"e_1_2_1_17_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1007\/978-3-642-04128-0_11"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/200836.200853"},{"volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM-SIAM, 472--473","year":"2002","author":"Chan T. M.","key":"e_1_2_1_20_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1016\/j.ipl.2008.02.008"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1137\/07068669X"},{"unstructured":"Chan T. M. and P&amp;#462;tra&amp;#351;cu M. 2010. Transdichotomous results in computational geometry II: Offline search. arXiv:1010.1948 (see also STOC 2007).  Chan T. M. and P&amp;#462;tra&amp;#351;cu M. 2010. Transdichotomous results in computational geometry II: Offline search. arXiv:1010.1948 (see also STOC 2007).","key":"e_1_2_1_23_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1137\/0221041"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1007\/s00453-002-0939-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/1542362.1542374"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.5555\/3116272.3116507"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1007\/BF02526034"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1109\/SFCS.1983.16"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1007\/BF02187740"},{"unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2009. Introduction to Algorithms 3rd Ed. MIT Press Cambridge MA.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2009. Introduction to Algorithms 3rd Ed. MIT Press Cambridge MA.","key":"e_1_2_1_31_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.5555\/1370949"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1006\/jagm.1995.1010"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1142\/S0218195995000192"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1016\/0020-0190(77)90031-X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1007\/BF01683268"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1016\/0304-3975(76)90078-5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1016\/0022-0000(93)90040-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1145\/800057.808675"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1016\/j.jalgor.2003.09.001"},{"volume-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 135--144","author":"Han Y.","key":"e_1_2_1_41_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1137\/0213024"},{"volume-title":"Proceedings of the 12th Canad. Conf. Comput. Geom. (CCCG). CCCG, 181--186","author":"Iacono J.","key":"e_1_2_1_43_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1145\/1141911.1141992"},{"unstructured":"Karlsson R. G. 1985. Algorithms in a Restricted Universe. Ph.D. dissertation University of Waterloo.   Karlsson R. G. 1985. Algorithms in a Restricted Universe. Ph.D. dissertation University of Waterloo.","key":"e_1_2_1_45_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.1007\/BF01934088"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1016\/0304-3975(83)90023-3"},{"volume":"52","volume-title":"MSRI Publications","author":"Liu Y.","key":"e_1_2_1_48_1"},{"volume-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium Discrete Algorithms (SODA). ACM-SIAM, 1759--1777","author":"Mulzer W","key":"e_1_2_1_49_1"},{"key":"e_1_2_1_50_1","volume-title":"Monographs in Theoretical Computer Science. An EATCS Series","volume":"1","author":"Mehlhorn K.","year":"1984"},{"doi-asserted-by":"publisher","key":"e_1_2_1_51_1","DOI":"10.1145\/256292.256294"},{"unstructured":"Morton G. 1966. A computer oriented geodetic data base and a new technique in file sequencing. Tech. rep. IBM Ltd. Ottawa Canada.  Morton G. 1966. A computer oriented geodetic data base and a new technique in file sequencing. Tech. rep. IBM Ltd. Ottawa Canada.","key":"e_1_2_1_52_1"},{"doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge UK.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge UK.","key":"e_1_2_1_53_1","DOI":"10.1017\/CBO9780511814075"},{"volume-title":"Computational Geometry: An Introduction through Randomized Algorithms","year":"1994","author":"Mulmuley K.","key":"e_1_2_1_54_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_55_1","DOI":"10.1016\/0020-0190(84)90116-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_56_1","DOI":"10.15807\/jorsj.27.306"},{"unstructured":"Overmars M. H. 1987. Computational geometry on a grid: An overview. Tech. rep. RUU-CS-87-04 Rijksuniversiteit Utrecht.  Overmars M. H. 1987. Computational geometry on a grid: An overview. Tech. rep. RUU-CS-87-04 Rijksuniversiteit Utrecht.","key":"e_1_2_1_57_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_58_1","DOI":"10.5555\/4333"},{"doi-asserted-by":"publisher","key":"e_1_2_1_59_1","DOI":"10.5555\/647906.739794"},{"volume-title":"Proceedings of the 6th International Colloquium on Automata Language Programming (ICALP). Springer-Verlag, 520--529","year":"1979","author":"Sch","key":"e_1_2_1_60_1"},{"unstructured":"Seidel R. 1984. A method for proving lower bounds for certain geometric problems. Tech. rep. TR84-592 Cornell University Ithaca NY.   Seidel R. 1984. A method for proving lower bounds for certain geometric problems. Tech. rep. TR84-592 Cornell University Ithaca NY.","key":"e_1_2_1_61_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_62_1","DOI":"10.1016\/S0925-7721(96)00025-9"},{"volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM-SIAM, 550--555","year":"1998","author":"Thorup M.","key":"e_1_2_1_63_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_64_1","DOI":"10.1007\/978-3-540-92182-0_49"},{"unstructured":"van Leeuwen J. and Tsakalides A. 1988. An optimal pointer machine algorithm for finding nearest common ancestors. Tech. rep. RUU-CS-88-17 Department of Information and Computing Sciences Utrecht University.  van Leeuwen J. and Tsakalides A. 1988. An optimal pointer machine algorithm for finding nearest common ancestors. Tech. rep. RUU-CS-88-17 Department of Information and Computing Sciences Utrecht University.","key":"e_1_2_1_65_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_66_1","DOI":"10.5555\/337729.337809"},{"doi-asserted-by":"publisher","key":"e_1_2_1_67_1","DOI":"10.5555\/1056214.1710876"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944345.1944347","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1944345.1944347","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:30Z","timestamp":1750244370000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944345.1944347"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4]]},"references-count":67,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["10.1145\/1944345.1944347"],"URL":"https:\/\/doi.org\/10.1145\/1944345.1944347","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2011,4]]},"assertion":[{"value":"2009-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}