On the size of chromatic Delaunay mosaics
Biswas R, Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2026. On the size of chromatic Delaunay mosaics. Discrete and Computational Geometry. 75, 24–47.
Download
Journal Article
| Published
| English
Scopus indexed
Author
Corresponding author has ISTA affiliation
Department
Grant
Abstract
Given a locally finite set A⊆Rd and a coloring χ:A→{0,1,…,s}, we introduce the chromatic Delaunay mosaic of χ, which is a Delaunay mosaic in Rs+d that represents how points of different colors mingle. Our main results are bounds on the size of the chromatic Delaunay mosaic, in which we assume that d and s are constants. For example, if A is finite with n=#A, and the coloring is random, then the chromatic Delaunay mosaic has O(n⌈d/2⌉) cells in expectation. In contrast, for Delone sets and Poisson point processes in Rd, the expected number of cells within a closed ball is only a constant times the number of points in this ball. Furthermore, in R2 all colorings of a dense set of n points have chromatic Delaunay mosaics of size O(n). This encourages the use of chromatic Delaunay mosaics in applications.
Publishing Year
Date Published
2026-01-01
Journal Title
Discrete and Computational Geometry
Publisher
Springer Nature
Acknowledgement
The fourth author thanks Boris Aronov for insightful discussions on the size of the overlay of Voronoi tessellations. Open access funding provided by Institute of Science and Technology (IST Austria). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35.
Volume
75
Page
24-47
ISSN
eISSN
IST-REx-ID
Cite this
Biswas R, Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. On the size of chromatic Delaunay mosaics. Discrete and Computational Geometry. 2026;75:24-47. doi:10.1007/s00454-025-00778-7
Biswas, R., Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., & Saghafian, M. (2026). On the size of chromatic Delaunay mosaics. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-025-00778-7
Biswas, Ranita, Sebastiano Cultrera di Montesano, Ondrej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. “On the Size of Chromatic Delaunay Mosaics.” Discrete and Computational Geometry. Springer Nature, 2026. https://doi.org/10.1007/s00454-025-00778-7.
R. Biswas, S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, “On the size of chromatic Delaunay mosaics,” Discrete and Computational Geometry, vol. 75. Springer Nature, pp. 24–47, 2026.
Biswas R, Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2026. On the size of chromatic Delaunay mosaics. Discrete and Computational Geometry. 75, 24–47.
Biswas, Ranita, et al. “On the Size of Chromatic Delaunay Mosaics.” Discrete and Computational Geometry, vol. 75, Springer Nature, 2026, pp. 24–47, doi:10.1007/s00454-025-00778-7.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2026_DiscreteCompGeom_Biswas.pdf
570.92 KB
Access Level
Open Access
Date Uploaded
2026-01-05
MD5 Checksum
0addb5c1b78142f9fb453bfa04695400
Export
Marked PublicationsOpen Data ISTA Research Explorer
Web of Science
View record in Web of Science®Sources
arXiv 2212.03121
Google Scholar