Name
Abstract | ||
|---|---|---|
Helly's theorem is a fundamental result in discrete geometry, describing the ways in which convex sets intersect with each other. If S is a set of n points in R-d, we say that S is (k, G)-clusterable if it can be partitioned into k clusters (subsets) such that each cluster can be contained in a translated copy of a geometric object G. In this paper, as an application of Helly's theorem, by taking a constant size sample from S, we present a testing algorithm for (k, G)clustering, i.e., to distinguish between two cases: when S is (k, G)-clusterable, and when it is epsilon-far from being (k, G)-clusterable. A set S is epsilon-far (0 < epsilon <= 1) from being (k, G)-clusterable if at least epsilon n points need to be removed from S to make it (k, G)-clusterable. We solve this problem for k = 1 and when G is a symmetric convex object. For k > 1, we solve a weaker version of this problem. Finally, as an application of our testing result, in clustering with outliers, we show that one can find the approximate clusters by querying a constant size sample, with high probability. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-642-54423-1_27 | Lecture Notes in Computer Science |
DocType | Volume | ISSN |
Conference | 8392 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sourav Chakraborty | 1 | 381 | 49.27 |
| Rameshwar Pratap | 2 | 6 | 4.50 |
| Sasanka Roy | 3 | 5 | 1.49 |
| Shubhangi Saraf | 4 | 263 | 24.55 |