Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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

On Conflict-Free Colorings

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:   2024  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