Name
Abstract | ||
|---|---|---|
A set of k balls B1, …,Bk in a Euclidean space is said to cover a collection of lines if every line intersects some ball. We consider the k-center problem for lines in high-dimensional space: Given a set of n lines l= {l1,…,ln in Rd, find k balls of minimum radius which cover l. We present a 2-approximation algorithm for the cases k = 2, 3 of this problem, having running time quasi-linear in the number of lines and the dimension of the ambient space. Our result for 3-clustering is strongly based on a new result in discrete geometry that may be of independent interest: 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 Helly theorem is of a new type: it depends on ε-contracting the sets. In statistical practice, data is often incompletely specified; we consider lines as the most elementary case of incompletely specified data points. Clustering of data is a key primitive in nonparametric statistics. Our results provide a way of performing this primitive on incomplete data, as well as imputing the missing values. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1868237.1868246 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
cases k,<i>k</i>-center,n lines l,helly theorem,high dimension,euclidean space,k balls b1,k ball,high-dimensional space,incomplete data,clustering line,ambient space,lines,incompletely specified data point,clustering,discrete geometry,missing values | Discrete geometry,Data point,Ambient space,Discrete mathematics,Combinatorics,Helly's theorem,Ball (bearing),Euclidean space,Missing data,Cluster analysis,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 1 | 1549-6325 |
Citations | PageRank | References |
1 | 0.35 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jie Gao | 1 | 2174 | 155.61 |
| Michael Langberg | 2 | 867 | 65.83 |
| Leonard J. Schulman | 3 | 1328 | 136.88 |