Given a locally finite set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$A \subseteq {{\mathbb R}}^d$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo>⊆</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> and a coloring <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\chi :A \rightarrow \{0,1,\ldots ,s\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo>:</mo> <mi>A</mi> <mo stretchy="false">→</mo> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>s</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, we introduce the chromatic Delaunay mosaic of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\chi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>χ</mi> </math></EquationSource> </InlineEquation>, which is a Delaunay mosaic in <InlineEquation ID="IEq4"> <EquationSource Format="TEX">${{\mathbb R}}^{d+s}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <mi>d</mi> <mo>+</mo> <mi>s</mi> </mrow> </msup> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$n = {{\#}{A}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mrow> <mo>#</mo> <mi>A</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation>, and the coloring is random, then the chromatic Delaunay mosaic has <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$O(n^{{\lceil d/2 \rceil }})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mo>⌈</mo> <mi>d</mi> <mo stretchy="false">/</mo> <mn>2</mn> <mo>⌉</mo> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> cells in expectation. In contrast, for Delone sets and Poisson point processes in <InlineEquation ID="IEq7"> <EquationSource Format="TEX">${{\mathbb R}}^d$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> </math></EquationSource> </InlineEquation>, the expected number of cells within a closed ball is only a constant times the number of points in this ball. Furthermore, in <InlineEquation ID="IEq8"> <EquationSource Format="TEX">${{\mathbb R}}^2$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mn>2</mn> </msup> </math></EquationSource> </InlineEquation> all colorings of a well spread set of n points have chromatic Delaunay mosaics of size O(n). This encourages the use of chromatic Delaunay mosaics in applications.

On the Size of Chromatic Delaunay Mosaics

期刊论文
出版模式：

开放获取
发表日期：

2025年9月30日

查看全文

Ranita Biswas,
Sebastiano Cultrera di Montesano,
Ondřej Draganov,
Herbert Edelsbrunner,
Morteza Saghafian

摘要

Given a locally finite set $A \subseteq {{\mathbb R}}^d$ $A \subseteq R^{d}$ and a coloring $\chi :A \rightarrow \{0,1,\ldots ,s\}$ $χ : A \to {0, 1, \dots, s}$ , we introduce the chromatic Delaunay mosaic of $\chi $ $χ$ , which is a Delaunay mosaic in ${{\mathbb R}}^{d+s}$ $R^{d + s}$ 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}}$ $n = # A$ , and the coloring is random, then the chromatic Delaunay mosaic has $O(n^{{\lceil d/2 \rceil }})$ $O (n^{⌈ d / 2 ⌉})$ cells in expectation. In contrast, for Delone sets and Poisson point processes in ${{\mathbb R}}^d$ $R^{d}$ , the expected number of cells within a closed ball is only a constant times the number of points in this ball. Furthermore, in ${{\mathbb R}}^2$ $R^{2}$ all colorings of a well spread set of n points have chromatic Delaunay mosaics of size O(n). This encourages the use of chromatic Delaunay mosaics in applications.