# Helly-Type Theorems in Property Testing

arXiv: https://arxiv.org/abs/1307.8268 · HTML: https://mlsanity.com/paper/1307.8268/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2013.

## Built on by (most cited first, 2 of 2)

- [Towards the mathematical foundation of the minimum enclosing ball and related problems](https://mlsanity.com/paper/2402.06629/) (2024)
- [Towards the methodology for solving the minimum enclosing ball and related problems](https://mlsanity.com/paper/2410.11063/) (2024)

## Abstract (arXiv)

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<ε≤1) 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>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.