Helly-type theorems in property testing

DOI10.1007/978-3-642-54423-1_27MaRDI QIDQ5405049zbMATH OpenOpenAlexFDO

Authors Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf

Publication date 31 March 2014

Published in LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.8268

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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<epsilonleq1)$ from being $(k,G)$-clusterable if at least $epsilonn$ 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.

Recommendations

• Helly-type theorems in property testing
• Discrete and lexicographic Helly-type theorems
• Testing of Clustering
• Helly’s theorem: New variations and applications
• On Helly's theorem: Algorithms and extensions

Cited in

(2)

• Helly-type theorems in property testing
• Untestable Properties in the Kahr-Moore-Wang Class

This page was built for publication: Helly-type theorems in property testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405049)