Sphere-of-influence graphs in normed spaces

Abstract

We show that any $k$-th closed sphere-of-influence graph in a $d$-dimensional normed space has a vertex of degree less than~$5^{d}k$, thus obtaining a common generalization of results of Füredi and Loeb (1994) and Guibas, Pach and Sharir (1994).

3 pages

Cited by in corpus (1)

• Combinatorial distance geometry in normed spaces