The sphere of influence graph of a set of points in the plane is a graph G(V, E) in which the vertex set V consists of the points, and the edge set E consists of edges joining two points if their nearest neighbor circles intersect. The nearest neighbor circle of a point P is the largest circle centered at P that does not contain any other points in its interior. This graph was proposed in 1980 as a geometric model for a primal sketch in computer vision. Since then it has been explored, generalized, and applied to problems in several disciplines. This paper traces the history of this graph, surveys the progress made since 1980, and lists areas for further research.
D. Avis, and J. Horton, “Remarks on the sphere of influence graph,” Discrete Geometry and Convexity (New York, 1982), pp. 323-327, Ann. New York Acad. Sci., 440, New York Acad. Sci., New York, 1985.
P. Bateman, and P. Erdős, “Geometrical extrema suggested by a lemma of Besicovitch,” American Mathematical Monthly, vol. 58, no. 5, pp. 306-314, 1951.
E. Boyer, L. Lister, and B. Shader, “Sphere-of-influence graphs using the sup-norm,” Mathematical and Computer Modelling, vol. 32, pp. 1071-1082, 2000.
T. Chalker, A. Godbole, P. Hitczenko, J. Radcliff, and O. Ruehr, “On the size of a random sphere of influence graph,” Advances in Applied Probability, vol. 31, pp. 596-609, 1999.
R. A. Dwyer, “The expected size of the sphere-of-influence graph,” Computational Geometry: Theory and Applications, vol. 5, pp. 155-164, 1995.
Z. Furedi, “The expected size of a random sphere of influence graph,” Intuitive Geometry, Bolyai Math. Soc., vol. 6, 319-326, 1995.
L. Guibas, J. Pach, and M. Sharir, “Sphere of influence graphs in higher dimensions,” Proc. Coll. Math. Soc. J. Bolyai, vol. 63, 131-137, 1994.
F. Harary, M. S. Jacobson, M. J. Lipman, and F. R. McMorris, “Abstract sphere-of-influence graphs,” Mathematical and Computer Modelling, vol. 17, no. 11, pp. 77-83, 1993.
P. Hitczenko, S. Janson, and J.E. Yukich, “On the variance of the random sphere of influence graph,” Random Structures and Algorithms, vol. 14, pp. 139-152, 1999.
J. W. Jaromczyk, and G. T. Toussaint, “Relative neighborhood graphs and their relatives,” Proceedings of the IEEE, vol. 80, no. 9, pp. 1502-1517, September 1992.
M. J. Lipman, “Integer realizations of sphere-of-influence graphs,” Congressus Numerantium, vol. 91, pp. 63-70, 1992.
D. Marr, “Early processing of visual information,” Philosophical Transactions Royal Society of London B, vol. 275, pp. 83-524, 1976.
T. S. Michael, and T. Quint, “Sphere of influence graphs and the L∞ metric,” Discrete Applied Mathematics, vol. 127, pp. 447-460, 2003.
T. S. Michael, and T. Quint, “Sphere of influence graphs in general metric spaces,” Mathematical and Computer Modelling, vol. 29, pp. 45-53, 1999.
T. S. Michael, and T. Quint, “Sphere of influence graphs: Edge density and clique size,” Mathematical and Computer Modelling, vol. 20, no. 7, pp. 19-24, 1994.
S. Palka, and M. Sperling, “On a sphere of influence graph in a one-dimensional space,” Discussiones Mathematicae, Graph Theory, vol. 25, pp. 427-433, 2005.
T. Poggio, “Marr’s computational approach to vision,” Neurosciences, vol. 4, no. 10, pp. 258-262, 1981.
E. R. Reifenberg, “A problem on circles,” Mathematical Gazette, vol. 32, pp. 290-292, 1948.
M. Sperling, “Vertices of degree one in a random sphere of influence graph,” Probability and Mathematical Statistics, vol. 20, no. 2, pp. 391-397, 2000.
M. Soss, “On the size of the Euclidean sphere of influence graph,” Proceedings of the Eleventh Canadian Conference on Computational Geometry, Vancouver, Canada, August 1999.
M. Soss, “The size of the open sphere of influence graph in L∞ metric spaces,” Proceedings of the Tenth Canadian Conference on Computational Geometry, Montreal, Canada, August 1998.
G. T. Toussaint, The Geometry of Musical Rhythm: What Makes a “Good” Rhythm Good? Chapman & Hall/CRC Press, Boca Raton: 2013.
G. T. Toussaint, “A graph-theoretical primal sketch,” in Computational Morphology, G. T. Toussaint, Ed., North-Holland, Amsterdam, 1988, pp. 229-260.
G. T. Toussaint, “Pattern recognition and geometrical complexity,” Proceedings Fifth International Conference on Pattern Recognition, Miami Beach, December 1980, pp. 1324-1347.
G. T. Toussaint, “The relative neighborhood graph of a finite planar set,” Pattern Recognition, vol. 12, pp. 261-268, 1980.
T. S. Holm, and K. P. Bogart, “On tolerance sphere-of-influence graphs,” Bulletin of the Institute of Combinatorics and its Applications, vol. 24, pp. 33-46, 1998.
A. E. Kézdy, and G. Kubicki, “K(12) is not a closed sphere-of-influence graph,” Intuitive geometry (Budapest, 1995), 383--397, Bolyai Soc. Math. Stud., 6, János Bolyai Math. Soc., Budapest, 1997.
T. A. McKee, and F. R. McMorris, Intersection Graph Theory, Monographs on Discrete Mathematics and Applications (Book 2), Society for Industrial and Applied Mathematics (February 1999).
M. Lipman, “Maximum tolerance sphere-of-influence graphs,” Congressus Numerantium, vol. 121, pp. 195-203, 1996.
M. S. Jacobson, M. J. Lipman, and F. R. McMorris, “Trees that are sphere-of-influence graphs,” Applied Mathematics Letters, vol. 8, no. 6, pp. 89-93, 1995.
F. Harary, M. S. Jacobson, M. J. Lipman, and F. R. McMorris, “Sphere of influence graphs defined on a prescribed graph,” International Conference on Graphs and Hypergraphs (Varenna, 1991), Journal of Combinatorics, Information & System Sciences, vol. 19, pp. 1-2, 5-10, 1994).
G. Chen, R. J. Gould, M. S. Jacobson, R. H. Schelp, and D. A. West, “A characterization of influence graphs of a prescribed graph,” Vishwa International Journal of Graph Theory, vol. 1, no. 1, pp. 77-81, 1992.
J. Klein, and G. Zachmann, “Point cloud surfaces using geometric proximity graphs,” Computers & Graphics, vol. 28, pp. 839-850, 2004.
D. Loshin, and A. Reifer, “Connectivity and spheres of influence,” in Using Information to Develop a Culture of Customer Centricity, Morgan Kaufmann, 2013, Chapter 5, pp. 32-38.
F. R. McMorris, and C. Wang, “Sphere-of-attraction graphs,” Congressus Numerantium, vol. 142, pp. 149- 160, 2000.
J. H. Levine, “The sphere of influence,” American Sociological Review, vol. 37, no. 1, pp. 14-27, 1972.
R. S. Bivand, “Creating neighbours,” vignette from: R. S. Bivand, E. Pebesma, and V. Gómez-Rubio, Applied Spatial Data Analysis, Springer-Verlag, New York, 2008, pp. 239-251.
B. M. Ábrego, R. Fabila-Monroy, S. Fernández-Merchand, D. Flores-Peñaloza, F. Hurtado, H. Meijer, V. Sacristán, and M. Saumell, “Proximity graphs inside large weighted graphs,” Networks, vol. 61, no. 1, pp. 29-39, 2013.
L. Sunil Chandran, R. Chitnis, and R. Kumar, “On the SIG-dimension of trees under the L∞-metric,” Graph and Combinatorics, vol. 29, pp. 773-794, 2013.