# Intersecting diametral balls induced by a geometric graph

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Aug 2021.

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

- [Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures](https://mlsanity.com/paper/2506.00165/) (2025)

## Abstract (arXiv)

For a graph whose vertex set is a finite set of points in the Euclidean d-space consider the closed (open) balls with diameters induced by its edges. The graph is called a (an open) Tverberg graph if these closed (open) balls intersect. Using the idea of halving lines, we show that (i) for any finite set of points in the plane, there exists a Hamiltonian cycle that is a Tverberg graph; (ii) for any  n  red and  n  blue points in the plane, there exists a perfect red-blue matching that is a Tverberg graph. Also, we prove that (iii) for any even set of points in the Euclidean  d -space, there exists a perfect matching that is an open Tverberg graph; (iv) for any  n  red and  n  blue points in the Euclidean  d -space, there exists a perfect red-blue matching that is a Tverberg graph.