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

Soss, Michael (1998) The Size of the Open Sphere of Influence Graph in L ∞ Metric Spaces. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 458-459 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_45).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_45
Classifications:Z Theory > Z.999 Others
Z Theory > Z.250 Geometry
ID Code:316

Repository Staff Only: item control page

References

D. Avis and J. Horton. Remarks on the sphere-of-influence graph. Discrete Geometry and Convexity, 440:323-327, 1985.

L. Guibas, J. Pach, and M. Sharir. Sphere-of-influence graphs in higher dimensions. Colloquia Mathematica Societatis Jànos Bolyai, 63:131-137, 1994.