Sphere of influence graphs in general metric spaces
Let X = {X-1,..., X-n} be a set of points in a metric space (n greater than or equal to 2). Let r(i) denote the minimum distance between X-i and the other points in X. The sphere of influence at X-i is the open ball with center X-i and radius r(i). The sphere of influence graph has vertex set X with an edge joining a pair of distinct vertices provided the corresponding spheres of influence intersect. This proximity graph was introduced by Toussaint to model computer vision and pattern recognition problems in the Euclidean plane. We discuss the abstract properties of sphere of influence graphs in general metric spaces with emphasis on normed linear spaces. Our work generalizes and simplifies some theorems in the literature on sphere of influence graphs and lays the groundwork for future work. (C) 1999 Elsevier Science Ltd. All rights reserved.
proximity graphs intersection graphs