The Size of the Open Sphere of Influence Graph in L ∞ Metric Spaces

Abstract

Let V be a set of distinct points in some metric space. For each point x ∈ V, let r x be the distance from x to its nearest neighbour, and let s x be the open ball centered at x with radius equal to the distance from x to its nearest neighbour. We refer to these balls as the spheres of influence of the set V. The open sphere of influence graph on V is defined as the graph where (x,y) is an edge if and only if s x and s y intersect.