{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T18:12:31Z","timestamp":1776881551511,"version":"3.51.2"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,9,8]],"date-time":"2020-09-08T00:00:00Z","timestamp":1599523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,8]],"date-time":"2020-09-08T00:00:00Z","timestamp":1599523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"European Research Council","award":["339025"],"award-info":[{"award-number":["339025"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p><jats:italic>Randomized incremental construction<\/jats:italic> (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms which are both simple and efficient in theory and in practice. Randomized incremental constructions are usually space-optimal and time-optimal in the worst case, as exemplified by the construction of convex hulls, Delaunay triangulations, and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst case. For example, it is known that the Delaunay triangulation of nicely distributed points in <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbb {E}}^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>E<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or on polyhedral surfaces in <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbb {E}}^3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>E<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> has linear complexity, as opposed to a worst-case complexity of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Theta (n^{\\lfloor d\/2\\rfloor })$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mo>\u230a<\/mml:mo>\n                        <mml:mi>d<\/mml:mi>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mo>\u230b<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in the first case and quadratic in the second. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the two cases above and variants of them, the complexity of the usual RIC is <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value. At the heart of our proof is a bound on the complexity of the Delaunay triangulation of random subsets of <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\varepsilon }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b5<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-nets. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.<\/jats:p>","DOI":"10.1007\/s00454-020-00235-7","type":"journal-article","created":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T08:20:47Z","timestamp":1599726047000},"page":"236-268","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets"],"prefix":"10.1007","volume":"66","author":[{"given":"Jean-Daniel","family":"Boissonnat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olivier","family":"Devillers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3055-9326","authenticated-orcid":false,"given":"Kunal","family":"Dutta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Glisse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,8]]},"reference":[{"key":"235_CR1","unstructured":"Amenta, N., Attali, D., Devillers, O.: Complexity of Delaunay triangulation for points on lower-dimensional polyhedra. In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1106\u20131113. ACM, New York (2007)"},{"issue":"4","key":"235_CR2","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/PL00009475","volume":"22","author":"N Amenta","year":"1999","unstructured":"Amenta, N., Bern, M.: Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22(4), 481\u2013504 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"235_CR3","doi-asserted-by":"crossref","unstructured":"Amenta, N., Choi, S., Rote, G.: Incremental constructions con BRIO. In: 19th Annual Symposium on Computational Geometry (San Diego 2003), pp. 211\u2013219. ACM, New York (2003)","DOI":"10.1145\/777792.777824"},{"issue":"3","key":"235_CR4","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s00454-003-2870-4","volume":"31","author":"D Attali","year":"2004","unstructured":"Attali, D., Boissonnat, J.-D.: A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces. Discrete Comput. Geom. 31(3), 369\u2013384 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"235_CR5","doi-asserted-by":"crossref","unstructured":"Attali, D., Boissonnat, J.-D., Lieutier, A.: Complexity of the Delaunay triangulation of points on surfaces the smooth case. In: 19th Annual Symposium on Computational Geometry (San Diego 2003), pp. 201\u2013210. ACM, New York (2003)","DOI":"10.1145\/777792.777823"},{"issue":"1","key":"235_CR6","first-page":"75","volume":"1910","author":"L Bieberbach","year":"1910","unstructured":"Bieberbach, L.: \u00dcber die Bewegungsgruppen des $$n$$-dimensionalen euklidischen Raumes mit einem endlichen Fundamentalbereich. Nachrichten von der Gesellschaft der Wissenschaften zu G\u00f6ttingen. Math.-Phys. Kl. 1910(1), 75\u201384 (1910)","journal-title":"Math.-Phys. Kl."},{"key":"235_CR7","unstructured":"Boileau, M., Maillot, S., Porti, J.: Three-Dimensional Orbifolds and Their Geometric Structures. Panoramas et Synth\u00e8ses, vol. 15. Soci\u00e9t\u00e9 Math\u00e9matique de France, Paris (2003)"},{"issue":"1\u20133","key":"235_CR8","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0925-7721(01)00048-7","volume":"22","author":"J-D Boissonnat","year":"2002","unstructured":"Boissonnat, J.-D., Cazals, F.: Smooth surface reconstruction via natural neighbour interpolation of distance functions. Comput. Geom. 22(1\u20133), 185\u2013203 (2002)","journal-title":"Comput. Geom."},{"key":"235_CR9","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.-D., Devillers, O., Hornus, S.: Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension. In: 25th Annual Symposium on Computational Geometry (Aarhus 2009), pp. 208\u2013216. ACM, New York (2009)","DOI":"10.1145\/1542362.1542403"},{"issue":"2","key":"235_CR10","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0304-3975(93)90024-N","volume":"112","author":"J-D Boissonnat","year":"1993","unstructured":"Boissonnat, J.-D., Teillaud, M.: On the randomized construction of the Delaunay tree. Theoret. Comput. Sci. 112(2), 339\u2013354 (1993)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"235_CR11","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1007\/s00454-016-9782-6","volume":"55","author":"M Caroli","year":"2016","unstructured":"Caroli, M., Teillaud, M.: Delaunay triangulations of closed Euclidean $$d$$-orbifolds. Discrete Comput. Geom. 55(4), 827\u2013853 (2016)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"235_CR12","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4(5), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"1792","key":"235_CR13","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1098\/rsta.2001.0956","volume":"360","author":"G De Fabritiis","year":"2002","unstructured":"De Fabritiis, G., Coveney, P.V., Flekk\u00f8y, E.G.: Multiscale dissipative particle dynamics. Philos. Trans. A Math. Phys. Eng. Sci. 360(1792), 317\u2013331 (2002)","journal-title":"Philos. Trans. A Math. Phys. Eng. Sci."},{"issue":"1","key":"235_CR14","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1142\/S021819599200007X","volume":"2","author":"O Devillers","year":"1992","unstructured":"Devillers, O.: Randomization yields simple $$O(n\\log ^\\ast \\!n)$$ algorithms for difficult $$\\Omega (n)$$ problems. Int. J. Comput. Geom. Appl. 2(1), 97\u2013111 (1992)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"2","key":"235_CR15","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1142\/S0129054102001035","volume":"13","author":"O Devillers","year":"2002","unstructured":"Devillers, O.: The Delaunay hierarchy. Int. J. Found. Comput. Sci. 13(2), 163\u2013180 (2002)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"235_CR16","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02574694","volume":"6","author":"RA Dwyer","year":"1991","unstructured":"Dwyer, R.A.: Higher-dimensional Voronoi diagrams in linear expected time. Discrete Comput. Geom. 6(4), 343\u2013367 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"235_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0898-1221(93)90068-7","volume":"26","author":"RA Dwyer","year":"1993","unstructured":"Dwyer, R.A.: The expected number of $$k$$-faces of a Voronoi diagram. Comput. Math. Appl. 26(5), 13\u201319 (1993)","journal-title":"Comput. Math. Appl."},{"issue":"1","key":"235_CR18","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s00454-003-2927-4","volume":"30","author":"J Erickson","year":"2003","unstructured":"Erickson, J.: Nice point sets can have nasty Delaunay triangulations. Discrete Comput. Geom. 30(1), 109\u2013132 (2003)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"235_CR19","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s00454-004-1089-3","volume":"33","author":"J Erickson","year":"2005","unstructured":"Erickson, J.: Dense point sets have sparse Delaunay triangulations or \u201c$$\\dots $$but not too nasty\u201d. Discrete Comput. Geom. 33(1), 83\u2013115 (2005)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"235_CR20","doi-asserted-by":"publisher","first-page":"958","DOI":"10.1214\/aoms\/1177704464","volume":"33","author":"EN Gilbert","year":"1962","unstructured":"Gilbert, E.N.: Random subdivisions of space into crystals. Ann. Math. Stat. 33(3), 958\u2013972 (1962)","journal-title":"Ann. Math. Stat."},{"issue":"3","key":"235_CR21","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0925-7721(02)00123-2","volume":"25","author":"MJ Golin","year":"2003","unstructured":"Golin, M.J., Na, H.-S.: On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes. Comput. Geom. 25(3), 197\u2013231 (2003)","journal-title":"Comput. Geom."},{"key":"235_CR22","first-page":"270","volume":"8","author":"JL Meijering","year":"1953","unstructured":"Meijering, J.L.: Interface area, edge length, and number of vertices in crystal aggregates with random nucleation. Philips Res. Rep. 8, 270\u2013290 (1953)","journal-title":"Philips Res. Rep."},{"key":"235_CR23","doi-asserted-by":"publisher","first-page":"243","DOI":"10.2307\/1425985","volume":"4","author":"RE Miles","year":"1972","unstructured":"Miles, R.E.: The random division of space. Adv. Appl. Probab. 4, 243\u2013266 (1972)","journal-title":"Adv. Appl. Probab."},{"issue":"3","key":"235_CR24","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/s00454-014-9629-y","volume":"52","author":"GL Miller","year":"2014","unstructured":"Miller, G.L., Sheehy, D.R.: A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations. Discrete Comput. Geom. 52(3), 476\u2013491 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"235_CR25","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Sheehy, D.R., Velingker, A.: A fast algorithm for well-spaced points and approximate Delaunay graphs. In: 29th Annual Symposium on Computational Geometry (Rio de Janeiro 2013), pp. 289\u2013298. ACM, New York (2013)","DOI":"10.1145\/2462356.2462404"},{"issue":"1","key":"235_CR26","doi-asserted-by":"publisher","first-page":"37","DOI":"10.2307\/1427197","volume":"21","author":"J M\u00f8ller","year":"1989","unstructured":"M\u00f8ller, J.: Random tessellations in $${\\mathbb{R}}^d$$. Adv. Appl. Probab. 21(1), 37\u201373 (1989)","journal-title":"Adv. Appl. Probab."},{"key":"235_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"235_CR28","volume-title":"Computational Geometry. An Introduction Through Randomized Algorithms.","author":"K Mulmuley","year":"1994","unstructured":"Mulmuley, K.: Computational Geometry. An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs (1994)"},{"key":"235_CR29","doi-asserted-by":"crossref","unstructured":"Robins, V.: Betti number signatures of homogeneous Poisson point processes. Phys. Rev. E 74(6), #\u00a0061107 (2006)","DOI":"10.1103\/PhysRevE.74.061107"},{"key":"235_CR30","unstructured":"Talmor, D.: Well-Spaced Points for Numerical Methods. PhD thesis, School of Computer Science, Carnegie Mellon University (1997)"},{"key":"235_CR31","doi-asserted-by":"crossref","unstructured":"Tihomirov, V.M.: $$\\varepsilon $$-entropy and $$\\varepsilon $$-capacity of sets in functional space. In: Selected Works of A.\u00a0N.\u00a0Kolmogorov. Vol. III: Information Theory and the Theory of Algorithms, pp. 86\u2013170. Springer, Dordrecht (1993)","DOI":"10.1007\/978-94-017-2973-4_7"},{"key":"235_CR32","volume-title":"Three-Dimensional Geometry and Topology","author":"WP Thurston","year":"2014","unstructured":"Thurston, W.P.: Three-Dimensional Geometry and Topology, vol. 1. Princeton University Press, Princeton (2014)"},{"issue":"10","key":"235_CR33","doi-asserted-by":"publisher","first-page":"2981","DOI":"10.1021\/jp076416h","volume":"112","author":"DR Weiss","year":"2008","unstructured":"Weiss, D.R., Raschke, T.M., Levitt, M.: How hydrophobic buckminsterfullerene affects surrounding water structure. J. Phys. Chem. B 112(10), 2981\u20132990 (2008)","journal-title":"J. Phys. Chem. B"},{"key":"235_CR34","doi-asserted-by":"crossref","unstructured":"van de Weygaert, R., Platen, E., Vegter, G., Eldering, B., Kruithof, N.: Alpha shape topology of the Cosmic Web. In: 7th International Symposium on Voronoi Diagrams in Science and Engineering (Quebec 2010), pp. 224\u2013234. IEEE Computer Society, Los Alamitos (2010)","DOI":"10.1109\/ISVD.2010.24"},{"key":"235_CR35","unstructured":"https:\/\/en.wikipedia.org\/wiki\/Volume_of_an_n-ball#Low_dimensions"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00235-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00235-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00235-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,7]],"date-time":"2021-09-07T23:37:01Z","timestamp":1631057821000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00235-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,8]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["235"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00235-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,8]]},"assertion":[{"value":"8 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}