Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 05.09.2006 at 12:20 in S6, there is the following noon lecture:

Clustering lines: classification of incomplete data

Leonard J. Schulman

Caltech

Abstract

A set of k balls B_1,...,B_k in Euclidean space is said to cover a collection of lines if every line intersects some ball. We consider the k-center problem for lines: Given a set of n lines L={l_1,...,l_n} in R^d and a radius r, find k balls of radius r which cover L or answer that no such set of balls exists. Our main result is an \tilde{O}(n) -time (1+epsilon)-approximation algorithm for this problem for the cases k=2,3.

Our algorithm for 3-clustering is based on a new result in discrete geometry: a Helly-type theorem for collections of axis-parallel "crosses" in the plane. The family of crosses does not have finite Helly number in the usual sense. Our statement is of a new type, that depends on epsilon-contracting the sets.

Joint work with Jie Gao and Michael Langberg.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010