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.