Hitting sets online and unique-max coloring

3. We also consider two geometrically defined hypergraphs. The first one is defined by subsets of a given set of n points in the Euclidean plane that are induced by half-planes. The second hypergraph is defined by subsets of a given set of n points in the plane induced by unit discs. For these hypergraphs, the competitive ratio obtained by Alon et al. is O(log2n). For both cases, we introduce an algorithm with O(logn)-competitive ratio. We also show that any online algorithm for both settings has a competitive ratio of Ω(logn), and hence our algorithms are optimal.