Shakhar Smorodinsky

Given a set of points in or , we aim to color them such that every region of a certain family (for instance disks) containing at least a certain number of points contains points of many different colors. Using k colors, it is not always possible to ensure that every region containing k points contains all k colors. Thus, we introduce two relaxations: either we allow the number of colors to increase to c(k), or we require that the number of points in each region increases to p(k). We give upper bounds on c(k) and p(k) for halfspaces, disks, and pseudo-disks. We also consider the dual question, where we want to color regions instead of points. This is related to previous results of Pach, Tardos and Tóth on decompositions of coverings.