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

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Friday, May 06, 2005, 12:15 pm

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

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

**Speaker**: Shakhar Smorodinsky (Courant Inst., New York Univ.)

A finite family R of simple Jordan regions in the plane defines a hypergraph H=H(R) where the vertex set of H is R and the hyperedges are all subsets S ⊆ R for which there is a point p such that S = {r ∈ R | p ∈ r }. The chromatic number of H(R) is the minimum number of colors needed to color the members of R such that no hyperedge of H(R) is monochromatic. We study the chromatic number of hypergraps that are defined by natural geometric instances such as discs, pseudo discs, axis-parallel rectangles etc. We obtain simple deterministic polynomial time algorithms for coloring such hypergraphs with ``few'' colors and show how to apply these results to obtain simple deterministic polynomial time algorithms for conflict-free coloring of such regions (where we want the property, that each point that is covered by the regions, is contained in at least one region whose color is unique, i.e., distinct from colors of other regions containing this point) with ``few'' colors.

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