Helly-type theorems in property testing

Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 Rd, 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 ∈-far from being (k,G)-clusterable. A set S is ∈-far (0< ∈) from being (k,G)-clusterable if at least ∈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∈gt1, 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.

Original languageEnglish (US)
Title of host publicationLATIN 2014
Subtitle of host publicationTheoretical Informatics - 11th Latin American Symposium, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783642544224
StatePublished - 2014
Event11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay
Duration: Mar 31 2014Apr 4 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8392 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other11th Latin American Theoretical Informatics Symposium, LATIN 2014

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Helly-type theorems in property testing'. Together they form a unique fingerprint.

Cite this