On the size of chromatic Delaunay mosaics
Biswas R, Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2025. On the size of chromatic Delaunay mosaics. Discrete and Computational Geometry.
Download (ext.)
Journal Article
| Epub ahead of print
| 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
2025-09-30
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.
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. 2025. doi:10.1007/s00454-025-00778-7
Biswas, R., Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., & Saghafian, M. (2025). 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, 2025. 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. Springer Nature, 2025.
Biswas R, Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2025. On the size of chromatic Delaunay mosaics. Discrete and Computational Geometry.
Biswas, Ranita, et al. “On the Size of Chromatic Delaunay Mosaics.” Discrete and Computational Geometry, Springer Nature, 2025, doi:10.1007/s00454-025-00778-7.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2212.03121
Google Scholar