Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-14T11:17:03.505Z Has data issue: false hasContentIssue false
  • English
  • Français

On the size of a random sphere of influence graph

Part of: Stochastic processes Graph theory Combinatorial probability Geometric probability and stochastic geometry

Published online by Cambridge University Press:  01 July 2016

T. K. Chalker ,
A. P. Godbole ,
P. Hitczenko ,
J. Radcliff  and
O. G. Ruehr
T. K. Chalker*
Affiliation:
University of California, Los Angeles
A. P. Godbole*
Affiliation:
Michigan Technological University
P. Hitczenko*
Affiliation:
North Carolina State University
J. Radcliff*
Affiliation:
University of Michigan, Ann Arbor
O. G. Ruehr*
Affiliation:
Michigan Technological University
*
∗ Postal address: Department of Mathematics, University of California, Los Angeles, CA 90024, USA.
∗∗ Email address: [email protected]
∗∗∗ Postal address: Department of Mathematics, North Carolina State University, Raleigh, NC 27607, USA.
∗∗∗∗ Postal address: Department of Mathematics, University of Michigan, Ann Arbor, MI 48109, USA.
∗∗∗∗∗ Postal address: Department of Mathematical Sciences, Michigan Technological University, Houghton, MI 49931, USA.
Get access Rights & Permissions [Opens in a new window]

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

Azuma-Hoeffding inequalityrandom graphssphere of influence graphs

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry
Secondary: 60C05: Combinatorial probability 60G42: Martingales with discrete parameter 05C80: Random graphs
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 31 , Issue 3 , September 1999 , pp. 596 - 609
Copyright
Copyright © Applied Probability Trust 1999 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Avis, D. and Horton, J. (1985). Remarks on the sphere of influence graph. In Discrete Geometry and Convexity, ed. Goodman, J. E. et al. New York Academy of Sciences, New York, pp. 323–327.Google Scholar
Chalker, T. K. and Radcliff, J. (1995). REU Project Report, Michigan Tech University.Google Scholar
Dwyer, R. A. (1995). The expected size of the sphere-of-influence graph. Computational Geometry: Theory and Applications 5, 155–164.CrossRefGoogle Scholar
Füredi, Z. and Loeb, P. A. (1994). On the best constant for the Besicovitch covering theorem. Proc. Amer. Math. Soc. 121, 1063–1073.CrossRefGoogle Scholar
Guibas, L., Pach, J. and Sharir, M. (1994). Sphere-of-influence graphs in higher dimensions. In Intuitive Geometry, Colloq. Math. Soc. János Bolyai 63, eds. Böröczky, K. and Töth, G.. János Bolyai Mathematical Society, Budapest, pp. 131–137.Google Scholar
Hall, P. (1988). Introduction to the Theory of Coverage Processes. Wiley, New York.Google Scholar
Michael, T. S. and Quint, T. (1994). Sphere of influence graphs: a survey. Congressus Numerantium 105, 153–160.Google Scholar
Shamir, E. and Spencer, J. (1987). Sharp concentration of the chromatic number in random graphs G_{n,p}. Combinatorica 7, 121–129.Google Scholar
Steele, J. M. (1997). Probability Theory and Combinatorial Optimization NSF-CBMS Regional Research Conference Lecture Notes Series Vol. 69). Society for Industrial and Applied Mathematics, Philadelphia, PA.Google Scholar
Talagrand, M. (1995). Concentration of measure and isoperimetric inequalities in product spaces. Publications Math. IHES 81, 73–205.Google Scholar
Toussaint, G. T. (1980). Pattern recognition and geometric complexity. In Proceedings of the 5th International Conference on Pattern Recognition, pp. 1324–1347. IEEE Computer Society Press, Washington DC.Google Scholar