Balázs Keszegh
Coloring geometric hypergraphs
Given a point set P in the plane, how many colors are needed to color the points of P such that whenever a disc covers at least two points of P then it covers two differently colored points as well? More generally, given some type of regions F (eg. all discs in the plane) and a point set P, we define H(F,P) as a hypergraph having P as its base set and a subset S is a hyperedge of H if and only if there exists a region R from F such that R's intersection with P equals to S. Our aim is to bound the chromatic number of such hypergraphs. We list results concerning hypergraphs defined by discs, axis-parallel rectangles, half-planes, translates of a given polygon, etc.. We also investigate relations to other topics, such as the dual problem when we color regions instead of points, cover-decomposability and confict-free colorings.