Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Tuesday, July 13, 2004, 12:15 pm

**Duration**: This information is not available in the database

**Location**: This information is not available in the database

**Speaker**: Shakhar Smorodinsky

Motivated by frequency assignment problems in cellular networks, we study some new coloring problems of the following flavor:

What is the minimum number *f(n)* such that one can assign colors to any set *P* of *n* points in the plane, using a total of at most *f(n)* colors
and such that this coloring have the following property (which we refer to
as Conflict Free coloring):
For any disc *d* in the plane, with nonempty intersection with *P*, there
is at least one point of *P* inside *d* which has a unique color among the
points inside *d*.
We show that *f(n) = O(log n)*
(As a nice warmup exercise you can think
on the restricted case where all points are on a line say, the *x*-axis).
This is asymptotically tight in the worst case.
We extend this result to many other classes of ranges (other than disks),
and also to the dual type of problems, where we want to color a given set
of ranges, so that for each point *p* there is a range with a unique color
among the ranges that contain *p*. We also present some challenging open
problems.

(Some parts of this talk is joint work with Guy Even, Zvika Lotker and Dana Ron (Tel Aviv University) and some other parts are joint work with Sariel Har-Peled (UIUC))

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login