Vertices of degree one in a random sphere of influence graph

• Autorzy: Sperling M.
• Języki publikacji: EN

Abstrakty

EN

The sphere of influence graph of the set of vertices in R^d is constructed by identifying the nearest neighbour of each vertex, centering a ball at each vertex so that its nearest neighbour lies on the boundary, and joining two vertices by an edge if and only if their balls intersect. We determine the expectation and variance of the number of vertices of degree one in the random sphere of influence graph.

Słowa kluczowe

EN

sphere of influence graph; variance of vertices of degree one; expected number of vertices of degree one

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2000
• Tom: Vol. 20, Fasc. 2
• Strony: 391--397
• Opis fizyczny: Bibliogr. 4 poz.

Twórcy

autor

Sperling M.

• Department of Discrete Mathematics, Adam Mickiewicz University, ul. Matejki 48/49, 60-769 Poznań, Poland

Bibliografia

• [1] R. A. Dwyer, The expected size of the sphere of influence graph, Computational Geometry 5 (1995), pp. 155-164.
• [2] Z. Füredi, The expected size of a random sphere of influence graph, Intuitive Geometry, Bolyai Mathematical Society 6 (1995), pp. 319-326.
• [3] Z. Füredi and P. A. Loeb, On the best constant on the Besicovitch covering theorem, Proc. Coll. Math. Soc. J. Bolyai 63 (1994), pp. 1063-1073.
• [4] P. Hitczenko, S. Janson and J. E. Yukich, On the variance of the random sphere of influence graph, Random Struct. Alg. 14 (1999), pp. 139-152.