On the size of a random sphere of influence graph
Authors:
- T. K. ChalkerTCT. K. Chalker
- A. P. GodboleAGA. P. Godbole
- P. HitczenkoPHP. Hitczenko
- J. RadcliffJRJ. Radcliff
- O. G. RuehrORO. G. Ruehr
- 1 September 1999
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 31 (3) , 596-609
Abstract
We approach sphere of influence graphs (SIGs) from a probabilistic perspective. Ordinary SIGs were first introduced by Toussaint as a type of proximity graph for use in pattern recognition, computer vision and other low-level vision tasks. A random sphere of influence graph (RSIG) is constructed as follows. Consider n points uniformly and independently distributed within the unit square in d dimensions. Around each point, Xi, draw an open ball (‘sphere of influence’) with radius equal to the distance to Xi's nearest neighbour. Finally, draw an edge between two points if their spheres of influence intersect. Asymptotically exact values for the expected number of edges in a RSIG are determined for all values of d; previously, just upper and lower bounds were known for this quantity. A modification of the Azuma-Hoeffding exponential inequality is employed to exhibit the sharp concentration of the number of edges around its expected value.Keywords
This publication has 6 references indexed in Scilit:
- Probability Theory and Combinatorial Optimization1997
- Concentration of measure and isoperimetric inequalities in product spacesPublications mathématiques de l'IHÉS, 1995
- The expected size of the sphere-of-influence graphComputational Geometry, 1995
- On the Best Constant for the Besicovitch Covering TheoremProceedings of the American Mathematical Society, 1994
- On the best constant for the Besicovitch covering theoremProceedings of the American Mathematical Society, 1994
- Sharp concentration of the chromatic number on random graphsG n, pCombinatorica, 1987