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