Coloring Delaunay-Edges and their Generalizations
Preprint
Abstract
We consider geometric hypergraphs whose vertex set is a finite set of points (e.g., in the plane), and whose hyperedges are the intersections of this set with a family of geometric regions (e.g., axis-parallel rectangles). A typical coloring problem for such geometric hypergraphs asks, given an integer $k$, for the existence of an integer $m=m(k)$, such that every set of points can be $k$-colored such that every hyperedge of size at least $m$ contains points of different (or all $k$) colors. We generalize this notion by introducing coloring of (unordered) \emph{$t$-tuples} of points such that every hyperedge that contains enough points contains $t$-tuples of different (or all) colors. In particular, we consider all $t$-tuples and $t$-tuples that are themselves hyperedges. The latter, with $t=2$, is equivalent to coloring the edges of the so-called \emph{Delaunay-graph}. In this paper we study colorings of Delaunay-edges with respect to halfplanes, pseudo-disks, axis-parallel and bottomless rectangles, and also discuss colorings of $t$-tuples of geometric and abstract hypergraphs, and connections between the standard coloring of vertices and coloring of $t$-tuples of vertices.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Unsplittable coverings in the planeAdvances in Mathematics, 2016
- Indecomposable Coverings with Homothetic PolygonsDiscrete & Computational Geometry, 2015
- On coloring points with respect to rectanglesJournal of Combinatorial Theory, Series A, 2013
- Coloring half-planes and bottomless rectanglesComputational Geometry, 2012
- Polychromatic coloring for half-planesJournal of Combinatorial Theory, Series A, 2012
- Octants Are Cover-DecomposableDiscrete & Computational Geometry, 2011
- Indecomposable Coverings with Concave PolygonsDiscrete & Computational Geometry, 2009
- Delaunay graphs of point sets in the plane with respect to axis‐parallel rectanglesRandom Structures & Algorithms, 2008
- Chromatic number of Hasse diagrams, eyebrows and dimensionOrder, 1991
- Concrete and Abstract Voronoi Diagrams1989