{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T11:30:19Z","timestamp":1768735819008,"version":"3.49.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,8,28]],"date-time":"2022-08-28T00:00:00Z","timestamp":1661644800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,28]],"date-time":"2022-08-28T00:00:00Z","timestamp":1661644800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["788183"],"award-info":[{"award-number":["788183"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["Z 342-N31"],"award-info":[{"award-number":["Z 342-N31"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["I 02979-N35"],"award-info":[{"award-number":["I 02979-N35"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-<jats:italic>k<\/jats:italic> mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order-<jats:italic>k<\/jats:italic> mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b1<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.<\/jats:p>","DOI":"10.1007\/s00453-022-01027-6","type":"journal-article","created":{"date-parts":[[2022,8,28]],"date-time":"2022-08-28T03:15:55Z","timestamp":1661656555000},"page":"277-295","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9823-6833","authenticated-orcid":false,"given":"Herbert","family":"Edelsbrunner","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8882-5116","authenticated-orcid":false,"given":"Georg","family":"Osang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,28]]},"reference":[{"issue":"3","key":"1027_CR1","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1137\/S0097539795281840","volume":"27","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., De Berg, M., Matousek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Comput. 27(3), 654\u2013667 (1998)","journal-title":"SIAM J. Comput."},{"key":"1027_CR2","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A Aggarwal","year":"1989","unstructured":"Aggarwal, A., Guibas, L.J., Saxe, J., Shor, P.W.: A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geom. 4, 591\u2013604 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"1027_CR3","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: Proceedings of the 19th Annual Symposium on Computational Geometry, pp. 201\u2013210 (2003)","DOI":"10.1145\/777792.777823"},{"key":"1027_CR4","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF02187788","volume":"5","author":"F Aurenhammer","year":"1990","unstructured":"Aurenhammer, F.: A new duality result concerning Voronoi diagrams. Discrete Comput. Geom. 5, 243\u2013254 (1990)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"1027_CR5","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1093\/comjnl\/24.2.162","volume":"24","author":"A Bowyer","year":"1981","unstructured":"Bowyer, A.: Computing Dirichlet tessellations. Comput. J. 24(2), 162\u2013166 (1981)","journal-title":"Comput. J."},{"issue":"6","key":"1027_CR6","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1007\/s10208-011-9098-0","volume":"11","author":"F Chazal","year":"2011","unstructured":"Chazal, F., Cohen-Steiner, D., M\u00e9rigot, Q.: Geometric inference for probability measures. Found. Comput. Math. 11(6), 733\u2013751 (2011)","journal-title":"Found. Comput. Math."},{"issue":"1","key":"1027_CR7","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(1), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"1027_CR8","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(3), 343\u2013367 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"1027_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, Heidelberg (1987)"},{"issue":"4","key":"1027_CR10","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1109\/TIT.1983.1056714","volume":"29","author":"H Edelsbrunner","year":"1983","unstructured":"Edelsbrunner, H., Kirkpatrick, D., Seidel, R.: On the shape of a set of points in the plane. IEEE Trans. Inf. Theory 29(4), 551\u2013559 (1983)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1027_CR11","unstructured":"Edelsbrunner, H., Osang, G.: The multi-cover persistence of Euclidean balls. In: Proceedings of the 34th Annual Symposium on Computational Geometry, pp. 34:1\u201334:14 (2018)"},{"issue":"1","key":"1027_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Seidel, R.: Voronoi diagrams and arrangements. Discrete Comput. Geom. 1(1), 25\u201344 (1986)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"1027_CR13","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."},{"issue":"1","key":"1027_CR14","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s00454-012-9465-x","volume":"49","author":"LJ Guibas","year":"2013","unstructured":"Guibas, L.J., Morozov, D., M\u00e9rigot, Q.: Witnessed $$k$$-distance. Discrete Comput. Geom. 49(1), 22\u201345 (2013)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20132","key":"1027_CR15","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.ipl.2013.07.023","volume":"114","author":"D Krasnoshchekov","year":"2014","unstructured":"Krasnoshchekov, D., Polishchuk, V.: Order-$$k$$$$\\alpha $$-hulls and $$\\alpha $$-shapes. Inform. Process. Lett. 114(1\u20132), 76\u201383 (2014)","journal-title":"Inform. Process. Lett."},{"issue":"6","key":"1027_CR16","first-page":"478","volume":"31","author":"D-T Lee","year":"1982","unstructured":"Lee, D.-T.: On $$k$$-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. 31(6), 478\u2013487 (1982)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"1027_CR17","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1112\/S0025579300002850","volume":"17","author":"P McMullen","year":"1970","unstructured":"McMullen, P.: The maximum numbers of faces of a convex polytope. Mathematika 17(2), 179\u2013184 (1970)","journal-title":"Mathematika"},{"key":"1027_CR18","doi-asserted-by":"crossref","unstructured":"Mulmuley, K.: Output sensitive construction of levels and Voronoi diagrams in $${\\mathbb{R}}^d$$ of order 1 to $$k$$. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 322\u2013330 (1990)","DOI":"10.1145\/100216.100259"},{"issue":"3","key":"1027_CR19","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02574692","volume":"6","author":"K Mulmuley","year":"1991","unstructured":"Mulmuley, K.: On levels in arrangements and Voronoi diagrams. Discrete Comput. Geom. 6(3), 307\u2013338 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"1027_CR20","unstructured":"Osang, G.: Higher order Delaunay mosaics in C++ and python. https:\/\/github.com\/geoo89\/orderkdelaunay (2019)"},{"key":"1027_CR21","unstructured":"Osang, G.: Rhomboid tiling and order-$$k$$ Delaunay mosaics in C++. https:\/\/github.com\/geoo89\/rhomboidtiling (2020)"},{"key":"1027_CR22","doi-asserted-by":"crossref","unstructured":"Shamos, M.I., Hoey, D.: Closest-point problems. In: Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science, pp. 151\u2013162 (1975)","DOI":"10.1109\/SFCS.1975.8"},{"key":"1027_CR23","unstructured":"The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 5.0 edition (2019)"},{"key":"1027_CR24","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1093\/comjnl\/24.2.167","volume":"24","author":"DF Watson","year":"1981","unstructured":"Watson, D.F.: Computing the n-dimensional Delaunay tesselation with application to Voronoi polytopes. Comput. J. 24, 167\u2013172 (1981)","journal-title":"Comput. J."},{"key":"1027_CR25","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BFb0038202","volume-title":"Results and New Trends in Computer Science","author":"E Welzl","year":"1991","unstructured":"Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: Maurer, H.A. (ed.) Results and New Trends in Computer Science, pp. 359\u2013370. Springer, New York (1991)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01027-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01027-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01027-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T12:06:05Z","timestamp":1674043565000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01027-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,28]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1027"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01027-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,28]]},"assertion":[{"value":"5 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}