Abstract

We consider proper online colorings of hypergraphs defined by geometric regions. We prove that there is an online coloring algorithm that colors NN intervals of the real line using Θ(log⁡N/k)Θ(\log N/k) colors such that for every point pp, contained in at least kk intervals, not all the intervals containing pp have the same color. We also prove the corresponding result about online coloring a family of wedges (quadrants) in the plane that are the translates of a given fixed wedge. These results contrast the results of the first and third author showing that in the quasi-online setting 12 colors are enough to color wedges (independent of NN and kk). We also consider quasi-online coloring of intervals. In all cases we present efficient coloring algorithms.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.