Combinatorial Algorithms Day

Abstract:
We initiate the study of adaptive computational geometry. We call an algorithm adaptive if it runs faster if a given input is "closer" to the desired output. Adaptive algorithms have been extensively studied for the sorting problem, and in this work we generalize the framework to geometric problems. As case studies, we look at the 2-dimensional convex hull computation and the 2-dimensional kd-tree construction.

Abstract:
Positive min-degree game goes as follows. There are two players, Maker and Breaker, and the game is played on the edges of a graph G. Players alternately claim edges of G, Breaker goes first, and Maker's goal is to have positive min-degree at the end of the game (i.e., to touch every vertex). We will address the following question: What is the sparsest graph G on which Maker can win the game?

Abstract:
In FOCS 2002, Even et al. showed that any set of n discs in the plane can be conflict-free colored with a total of at most O(log n) colors. Namely, it can be colored with O(log n) colors such that for any (covered) point p there is some disc whose color is distinct from all other colors of discs containing p. They also showed that this bound is asymptotically tight.
We prove the following stronger result: Any set of n discs in the plane can be colored with a total of at most O(k log n) colors such that for any point p that is covered by at least k discs, there are at least k distinct discs each of which is colored by a color distinct from all other discs containing p and for any point p covered by at most k discs, all discs covering p are colored distinctively. We call such a coloring a k-strong conflict-free coloring. We extend this result to pseudo-discs and arbitrary regions with linear union-complexity.
Joint work with Elad Horev and Roi Krakovski.