Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915234692726784 |
|---|---|
| author | Bae, Sang Won Oliver, Nicolau Papadopoulou, Evanthia |
| author_facet | Bae, Sang Won Oliver, Nicolau Papadopoulou, Evanthia |
| contents | Given a set $S$ of $n$ colored sites, each $s\in S$ associated with a distance-to-site function $δ_s \colon \mathbb{R}^2 \to \mathbb{R}$, we consider two distance-to-color functions for each color: one takes the minimum of $δ_s$ for sites $s\in S$ in that color and the other takes the maximum. These two sets of distance functions induce two families of higher-order Voronoi diagrams for colors in the plane, namely, the minimal and maximal order-$k$ color Voronoi diagrams, which include various well-studied Voronoi diagrams as special cases. In this paper, we derive an exact upper bound $4k(n-k)-2n$ on the total number of vertices in both the minimal and maximal order-$k$ color diagrams for a wide class of distance functions $δ_s$ that satisfy certain conditions, including the case of point sites $S$ under convex distance functions and the $L_p$ metric for any $1\leq p \leq\infty$. For the $L_1$ (or, $L_\infty$) metric, and other convex polygonal metrics, we show that the order-$k$ minimal diagram of point sites has $O(\min\{k(n-k), (n-k)^2\})$ complexity, while its maximal counterpart has $O(\min\{k(n-k), k^2\})$ complexity. To obtain these combinatorial results, we extend the Clarkson--Shor framework to colored objects, and demonstrate its application to several fundamental geometric structures, including higher-order color Voronoi diagrams, colored $j$-facets, and levels in the arrangements of piecewise linear/algebraic curves/surfaces. We also present an iterative approach to compute higher-order color Voronoi diagrams. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06960 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework Bae, Sang Won Oliver, Nicolau Papadopoulou, Evanthia Computational Geometry Given a set $S$ of $n$ colored sites, each $s\in S$ associated with a distance-to-site function $δ_s \colon \mathbb{R}^2 \to \mathbb{R}$, we consider two distance-to-color functions for each color: one takes the minimum of $δ_s$ for sites $s\in S$ in that color and the other takes the maximum. These two sets of distance functions induce two families of higher-order Voronoi diagrams for colors in the plane, namely, the minimal and maximal order-$k$ color Voronoi diagrams, which include various well-studied Voronoi diagrams as special cases. In this paper, we derive an exact upper bound $4k(n-k)-2n$ on the total number of vertices in both the minimal and maximal order-$k$ color diagrams for a wide class of distance functions $δ_s$ that satisfy certain conditions, including the case of point sites $S$ under convex distance functions and the $L_p$ metric for any $1\leq p \leq\infty$. For the $L_1$ (or, $L_\infty$) metric, and other convex polygonal metrics, we show that the order-$k$ minimal diagram of point sites has $O(\min\{k(n-k), (n-k)^2\})$ complexity, while its maximal counterpart has $O(\min\{k(n-k), k^2\})$ complexity. To obtain these combinatorial results, we extend the Clarkson--Shor framework to colored objects, and demonstrate its application to several fundamental geometric structures, including higher-order color Voronoi diagrams, colored $j$-facets, and levels in the arrangements of piecewise linear/algebraic curves/surfaces. We also present an iterative approach to compute higher-order color Voronoi diagrams. |
| title | Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2504.06960 |