{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T14:30:14Z","timestamp":1767018614001,"version":"3.48.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T00:00:00Z","timestamp":1759190400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T00:00:00Z","timestamp":1759190400000},"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"}]},{"DOI":"10.13039\/100014988","name":"Institute of Science and Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100014988","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Given a locally finite set\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$A \\subseteq {{\\mathbb R}}^d$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>A<\/mml:mi>\n                            <mml:mo>\u2286<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>R<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>d<\/mml:mi>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and a coloring\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\chi :A \\rightarrow \\{0,1,\\ldots ,s\\}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03c7<\/mml:mi>\n                            <mml:mo>:<\/mml:mo>\n                            <mml:mi>A<\/mml:mi>\n                            <mml:mo>\u2192<\/mml:mo>\n                            <mml:mo>{<\/mml:mo>\n                            <mml:mn>0<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mo>\u2026<\/mml:mo>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>s<\/mml:mi>\n                            <mml:mo>}<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , we introduce the\n                    <jats:italic>chromatic Delaunay mosaic<\/jats:italic>\n                    of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\chi $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03c7<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , which is a Delaunay mosaic in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$${{\\mathbb R}}^{d+s}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>R<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>d<\/mml:mi>\n                              <mml:mo>+<\/mml:mo>\n                              <mml:mi>s<\/mml:mi>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    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\n                    <jats:italic>d<\/jats:italic>\n                    and\n                    <jats:italic>s<\/jats:italic>\n                    are constants. For example, if\n                    <jats:italic>A<\/jats:italic>\n                    is finite with\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n = {{\\#}{A}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mo>#<\/mml:mo>\n                              <mml:mi>A<\/mml:mi>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , and the coloring is random, then the chromatic Delaunay mosaic has\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n^{{\\lceil d\/2 \\rceil }})$$<\/jats:tex-math>\n                        <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:msup>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mrow>\n                                <mml:mo>\u2308<\/mml:mo>\n                                <mml:mi>d<\/mml:mi>\n                                <mml:mo>\/<\/mml:mo>\n                                <mml:mn>2<\/mml:mn>\n                                <mml:mo>\u2309<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    cells in expectation. In contrast, for Delone sets and Poisson point processes in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$${{\\mathbb R}}^d$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>R<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mi>d<\/mml:mi>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , the expected number of cells within a closed ball is only a constant times the number of points in this ball. Furthermore, in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$${{\\mathbb R}}^2$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>R<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    all colorings of a well spread set of\n                    <jats:italic>n<\/jats:italic>\n                    points have chromatic Delaunay mosaics of size\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    ). This encourages the use of chromatic Delaunay mosaics in applications.\n                  <\/jats:p>","DOI":"10.1007\/s00454-025-00778-7","type":"journal-article","created":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T17:55:00Z","timestamp":1759254900000},"page":"24-47","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Size of Chromatic Delaunay Mosaics"],"prefix":"10.1007","volume":"75","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5372-7890","authenticated-orcid":false,"given":"Ranita","family":"Biswas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6249-0832","authenticated-orcid":false,"given":"Sebastiano Cultrera di","family":"Montesano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0464-3823","authenticated-orcid":false,"given":"Ond\u0159ej","family":"Draganov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9823-6833","authenticated-orcid":false,"given":"Herbert","family":"Edelsbrunner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4201-5775","authenticated-orcid":false,"given":"Morteza","family":"Saghafian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,30]]},"reference":[{"key":"778_CR1","doi-asserted-by":"publisher","DOI":"10.1142\/8685","volume-title":"Voronoi Diagrams and Delaunay Triangulations","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer, F., Klein, R., Lee, D.-T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Singapore (2013)"},{"key":"778_CR2","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1038\/s41591-018-0014-x","volume":"24","author":"M Binnewies","year":"2018","unstructured":"Binnewies, M., et al.: Understanding the tumor immune microenvironment (TIME) for effective therapy. Nat. Med. 24, 541\u2013550 (2018)","journal-title":"Nat. Med."},{"key":"778_CR3","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1090\/S0273-0979-09-01249-X","volume":"46","author":"G Carlsson","year":"2009","unstructured":"Carlsson, G.: Topology and data. Bull. New Ser. Am. Math. Soc. 46, 255\u2013308 (2009)","journal-title":"Bull. New Ser. Am. Math. Soc."},{"key":"778_CR4","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0925-7721(01)00021-9","volume":"19","author":"H-L Cheng","year":"2001","unstructured":"Cheng, H.-L., Edelsbrunner, H., Fu, P.: Shape space from deformation. Comput. Geom. Theory Appl. 19, 191\u2013204 (2001)","journal-title":"Comput. Geom. Theory Appl."},{"key":"778_CR5","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.: Applications of random sampling. Discrete Comput. Geom. 4, 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"778_CR6","doi-asserted-by":"crossref","unstructured":"Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., Saghafian, M.: Chromatic alpha complexes. Found Data Sci. https:\/\/doi.org\/10.3934\/fods.2025003 (2024)","DOI":"10.3934\/fods.2025003"},{"key":"778_CR7","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, 343\u2013367 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"778_CR8","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, 13\u201319 (1993)","journal-title":"Comput. Math. Appl."},{"key":"778_CR9","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/77635.77639","volume":"9","author":"H Edelsbrunner","year":"1990","unstructured":"Edelsbrunner, H., M\u00fccke, E.P.: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graphics 9, 66\u2013104 (1990)","journal-title":"ACM Trans. Graphics"},{"key":"778_CR10","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/174462.156635","volume":"13","author":"H Edelsbrunner","year":"1994","unstructured":"Edelsbrunner, H., M\u00fccke, E.P.: Three-dimensional alpha shapes. ACM Trans. Graphics 13, 43\u201372 (1994)","journal-title":"Three-dimensional alpha shapes. ACM Trans. Graphics"},{"key":"778_CR11","first-page":"746","volume":"64","author":"H Edelsbrunner","year":"2019","unstructured":"Edelsbrunner, H., Nikitenko, A.: Weighted Poisson-Delaunay mosaics. Theory Probab. Appl. 64, 746\u2013770 (2019)","journal-title":"Theory Probab. Appl."},{"key":"778_CR12","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1007\/s00454-018-0049-2","volume":"62","author":"H Edelsbrunner","year":"2019","unstructured":"Edelsbrunner, H., Nikitenko, A.: Poisson-Delaunay mosaics of order $$k$$. Discrete Comput. Geom. 62, 865\u2013878 (2019)","journal-title":"Discrete Comput. Geom."},{"key":"778_CR13","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... but not too nasty\u2019\u2019. Discrete Comput. Geom. 33, 83\u2013115 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"778_CR14","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. Statist. 33, 958\u2013972 (1962)","journal-title":"Ann. Math. Statist."},{"key":"778_CR15","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.: On the average complexity of 3d-Voronoi diagrams of random points on convex polytopes. Comput. Geom. 25, 197\u2013231 (2003)","journal-title":"Comput. Geom."},{"key":"778_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, 478\u2013487 (1982)","journal-title":"IEEE Trans. Comput."},{"key":"778_CR17","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":"778_CR18","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."},{"key":"778_CR19","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 $$R^d$$. Adv. Appl. Probab. 21, 37\u201373 (1989)","journal-title":"Adv. Appl. Probab."},{"key":"778_CR20","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1126\/science.1225399","volume":"338","author":"JL Ma\u00eetre","year":"2012","unstructured":"Ma\u00eetre, J.L., Berthoumieux, H., Krens, S.F., Salbreux, G., J\u00fclicher, F., Paluch, E., Heisenberg, C.-P.: Adhesion functions in cell sorting by mechanically coupling the cortices of adhering cells. Science 338, 253\u2013256 (2012)","journal-title":"Science"},{"key":"778_CR21","unstructured":"Pishro-Nik, H.: Introduction to Probability, Statistics, and Random Processes. Kappa Research, (2014)"},{"key":"778_CR22","first-page":"221","volume":"14","author":"Y Reani","year":"2023","unstructured":"Reani, Y., Bobrowski, O.: A coupled alpha complex. J. Comput. Geom. 14, 221\u2013256 (2023)","journal-title":"J. Comput. Geom."},{"key":"778_CR23","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1038\/s41586-021-03634-9","volume":"596","author":"A Rao","year":"2021","unstructured":"Rao, A., Barkley, D., Fran\u00e7a, G.S., Yanai, I.: Exploring tissue architecture using spatial transcriptomics. Nature 596, 211\u2013220 (2021)","journal-title":"Nature"},{"key":"778_CR24","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1038\/s41586-022-05672-3","volume":"614","author":"M Sorin","year":"2023","unstructured":"Sorin, M., Rezanejad, M., Karimi, E., Fiset, B., Desharnais, L., Perus, L.J.M., Milette, S., Yu, M.W., Maritan, S.M., Dor\u00e9, S., Pichette, \u00c9., Enlow, W., Gagn\u00e9, A., Wei, Y., Orain, M., Manem, V.S.K., Rayes, R., Siegel, P.M., Camilleri-Bro\u00ebt, S., Olivier Fiset, P., Desmeules, P., Spicer, J.D., Quail, D.F., Joubert, P., Walsh, L.A.: Single-cell spatial landscapes of the lung tumour immune microenvironment. Nature 614, 548\u2013554 (2023)","journal-title":"Nature"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00778-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-025-00778-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00778-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T14:26:50Z","timestamp":1767018410000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-025-00778-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,30]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["778"],"URL":"https:\/\/doi.org\/10.1007\/s00454-025-00778-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2025,9,30]]},"assertion":[{"value":"23 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}