PDF
Discussiones Mathematicae Graph Theory 25(3) (2005)
427-433
DOI: https://doi.org/10.7151/dmgt.1294
ON A SPHERE OF INFLUENCE GRAPH IN A ONE-DIMENSIONAL SPACE
Zbigniew Palka and Monika Sperling
Department of Algorithmics and Programming
Adam Mickiewicz University
Umultowska 87, 61-614 Poznań, Poland
e-mail: palka@amu.edu.pl
e-mail: dwight@amu.edu.pl
Abstract
A sphere of influence graph generated by a finite population of generated points on the real line by a Poisson process is considered. We determine the expected number and variance of societies formed by population of n points in a one-dimensional space.Keywords: cluster, sphere of influence graph.
2000 Mathematics Subject Classification: Primary 60D05;
Secondary 60C05, 05C80.
References
[1] | P. Avis and J. Horton, Remarks on the sphere of influence graph, in: ed. J.E. Goodman, et al. Discrete Geometry and Convexity (New York Academy of Science, New York) 323-327. |
[2] | T. Chalker, A. Godbole, P. Hitczenko, J. Radcliff and O. Ruehr, On the size of a random sphere of influence graph, Adv. in Appl. Probab. 31 (1999) 596-609, doi: 10.1239/aap/1029955193. |
[3] | E.G. Enns, P.F. Ehlers and T. Misi, A cluster problem as defined by nearest neighbours, The Canadian Journal of Statistics 27 (1999) 843-851, doi: 10.2307/3316135. |
[4] | Z. Furedi, The expected size of a random sphere of influence graph, Intuitive Geometry, Bolyai Math. Soc. 6 (1995) 319-326. |
[5] | Z. Furedi and P.A. Loeb, On the best constant on the Besicovitch covering theorem, in: Proc. Coll. Math. Soc. J. Bolyai 63 (1994) 1063-1073. |
[6] | P. Hitczenko, S. Janson and J.E. Yukich, On the variance of the random sphere of influence graph, Random Struct. Alg. 14 (1999) 139-152, doi: 10.1002/(SICI)1098-2418(199903)14:2<139::AID-RSA2>3.0.CO;2-E. |
[7] | L. Guibas, J. Pach and M. Sharir, Sphere of influence graphs in higher dimensions, in: Proc. Coll. Math. Soc. J. Bolyai 63 (1994) 131-137. |
[8] | T.S. Michael and T. Quint, Sphere of influence graphs: a survey, Congr. Numer. 105 (1994) 153-160. |
[9] | T.S. Michael and T. Quint, Sphere of influence graphs and the L∞-metric, Discrete Appl. Math. 127 (2003) 447-460, doi: 10.1016/S0166-218X(02)00246-9. |
[10] | Toussaint, Pattern recognition of geometric complexity, in: Proceedings of the 5th Int. Conference on Pattern Recognition, (1980) 1324-1347. |
[11] | D. Warren and E. Seneta, Peaks and eulerian numbers in a random sequence, J. Appl. Prob. 33 (1996) 101-114, doi: 10.2307/3215267. |
Received 9 September 2004
Revised 4 May 2005
Close