Coloring and Guarding Arrangements
Prosenjit Bose, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Matias Korman, Stefan Langerman, Perouz Taslakian
Abstract
Given a simple arrangement of lines in the plane, what is the minimum
number c of colors required so that we can color all
lines in a way that no cell of the arrangement is monochromatic? In
this paper we give worst-case bounds on the number c for
both the above question and for some of its variations. Line coloring
problems can be redefined as geometric hypergraph coloring problems as
follows: if we define
Hline-cell as the
hypergraph whose vertices are lines and edges are cells of the
arrangement, then c is equal to the chromatic number of
this hypergraph. Specifically, we prove that this chromatic number is
between Ω(log n / log log n) and
O(n). Furthermore, we give bounds on the
minimum size of a subset S of the intersection points
between pairs of lines in A such that
every cell contains at least a vertex of S. This may be
seen as the problem of guarding cells with vertices when the lines act
as obstacles. The problem can also be defined as the minimum vertex
cover problem in the hypergraph
Hvertex-cell, the vertices
of which are the line intersections, and the hyperedges are vertices
of a cell. Analogously, we consider the problem of touching the lines
with a minimum subset of the cells of the arrangement, which we
identify as the minimum vertex cover problem in the
Hcell-zone hypergraph.
Full Text: PDF PostScript