References#
This page lists the main theoretical, algorithmic, and software references used by the Proximity Graphs library.
Classical proximity graphs and computational geometry#
The Gabriel graph originates in the statistical geography work of Gabriel and Sokal [17], with later analysis by Matula and Sokal [26]. The relative neighborhood graph was introduced by Toussaint [35] and further surveyed by Jaromczyk and Toussaint [20].
Alpha-shapes and related shape reconstruction methods are associated with Edelsbrunner et al. [15], while computational morphology and related geometric frameworks are represented by Kirkpatrick and Radke [23], Radke [30], and Toussaint [32].
Several expected-size and structural results for geometric graphs are developed in Devroye [14], Cimikowski [9], Eppstein et al. [16], and Chalker et al. [8].
Voronoi diagrams and Delaunay triangulations are classical geometric structures used throughout the library; see Aurenhammer and Klein [4] and De Berg et al. [12].
Specialized proximity graph families#
Unit disk graphs are treated in Clark et al. [10].
The gamma-neighborhood graph implemented in this library follows Veltkamp [36].
Elliptic Gabriel graphs and empty-ellipse graphs are represented by Park et al. [29] and Devillers et al. [13].
Empty-region graphs and related locality frameworks are discussed in Cardinal et al. [7], Bose et al. [5], and Bose et al. [6].
Beta-skeleton behavior and spectral properties are represented by Adamatzky [1] and Alonso et al. [3].
Sphere-of-influence and relative-neighborhood applications are represented by Toussaint [34] and Toussaint [33].
For broader algorithmic background on proximity algorithms, see Mitchell and Mulzer [27].
Machine learning, clustering, and manifold learning#
Applications of proximity graphs to clustering and machine learning include Yang et al. [39] and Zemel and Carreira-Perpiñán [40].
Biological and adaptive networks#
The biologically inspired graph components are motivated by adaptive network models such as Tero et al. [31] and slime-mould transport approximations such as Adamatzky et al. [2].
Spatial networks, roads, and movement corridors#
Applications of proximity graphs to road networks and movement corridors are represented by Watanabe [38], Osaragi and Hiraga [28], Maniadakis and Varoutas [24], Kannangara et al. [21], and Kannangara et al. [22].
Software and scientific computing#
The library depends on standard scientific Python and graph-computing tools. Relevant software references include Csárdi and Nepusz [11], Hagberg et al. [18], Harris et al. [19], and Virtanen et al. [37].
General introductions#
For a general introduction to proximity graphs, see Mathieson and Moscato [25].
Bibliography#
Andrew Adamatzky. How β-skeletons lose their edges. Information Sciences, 254:213–224, 2014. URL: https://arxiv.org/abs/1312.7363, arXiv:1312.7363.
Andrew Adamatzky, Genaro J Martínez, Sergio V Chapa-Vergara, René Asomoza-Palacio, and Christopher R Stephens. Approximating Mexican highways with slime mould. Natural Computing, 10(3):1195–1214, 2011. doi:10.1007/s11047-011-9255-z.
Lázaro Alonso, JA Méndez-Bermúdez, and Ernesto Estrada. Geometrical and spectral study of β-skeleton graphs. Physical Review E, 100(6):062309, 2019. doi:10.1103/PhysRevE.100.062309.
Franz Aurenhammer and Rolf Klein. Voronoi diagrams. In J R Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 201–290. Elsevier Science, 2000. doi:10.1016/B978-044482537-7/50006-1.
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, and Michiel Smid. Sigma-local graphs. Journal of Discrete Algorithms, 8(1):15–23, 2010. doi:10.1016/j.jda.2008.10.002.
Prosenjit Bose, Vida Dujmović, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Vera Sacristán, Maria Saumell, and David R Wood. Proximity graphs: $e$, δ, δ, χ and ω. International Journal of Computational Geometry & Applications, 22(5):439–469, 2012. doi:10.1142/S0218195912500112.
Jean Cardinal, Sébastien Collette, and Stefan Langerman. Empty region graphs. Computational Geometry, 42(3):183–195, 2009. doi:10.1016/j.comgeo.2008.09.003.
TK Chalker, AP Godbole, P Hitczenko, J Radcliff, and OG Ruehr. On the size of a random sphere of influence graph. Advances in Applied Probability, 31(3):596–609, 1999. doi:10.1239/aap/1029955193.
Robert J Cimikowski. Properties of some euclidean proximity graphs. Pattern Recognition Letters, 13(6):417–423, 1992. doi:10.1016/0167-8655(92)90048-5.
Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete Mathematics, 86(1–3):165–177, 1990. doi:10.1016/0012-365X(90)90358-O.
Gábor Csárdi and Tamás Nepusz. The igraph software package for complex network research. InterJournal, Complex Systems:1695, 2006. URL: https://igraph.org.
Mark De Berg, Otfried Cheong, Marc Van Kreveld, and Mark Overmars. Delaunay Triangulations, chapter 9, pages 191–218. Springer, 2008. doi:10.1007/978-3-540-77974-2.
Olivier Devillers, Jeff Erickson, and Xavier Goaoc. Empty-ellipse graphs. In 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 1249–1256. 2008. doi:10.5555/1347082.1347218.
Luc Devroye. The expected size of some graphs in computational geometry. Computers & Mathematics with Applications, 15(1):53–64, 1988. doi:10.1016/0898-1221(88)90071-5.
Herbert Edelsbrunner, David Kirkpatrick, and Raimund Seidel. On the shape of a set of points in the plane. IEEE Transactions on Information Theory, 29(4):551–559, 1983. doi:10.1109/TIT.1983.1056714.
David Eppstein, Michael S. Paterson, and F. Frances Yao. On nearest-neighbor graphs. Discrete & Computational Geometry, 17:263–282, 1997. doi:10.1007/PL00009293.
K Ruben Gabriel and Robert R Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology, 18(3):259–278, 1969. doi:10.2307/2412323.
Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference, 11–15. 2008. doi:10.25080/TCWV9851.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, and others. Array programming with numpy. Nature, 585(7825):357–362, 2020. doi:10.1038/s41586-020-2649-2.
Jerzy W Jaromczyk and Godfried T Toussaint. Relative neighborhood graphs and their relatives. Proceedings of the IEEE, 80(9):1502–1517, 1992. doi:10.1109/5.163414.
Sameera Kannangara, Egemen Tanin, Aaron Harwood, and Shanika Karunasekera. Stepping stone graph for public movement analysis. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 149–158. 2018. doi:10.1145/3274895.3274913.
Sameera Kannangara, Egemen Tanin, Aaron Harwood, and Shanika Karunasekera. Stepping stone graph: a graph for finding movement corridors using sparse trajectories. ACM Transactions on Spatial Algorithms and Systems, 5(4):1–24, 2019. doi:10.1145/3324883.
David G. Kirkpatrick and John D. Radke. A framework for computational morphology. In Godfried T. Toussaint, editor, Computational Geometry, pages 217–248. 1985. doi:10.1016/B978-0-444-87806-9.50013-X.
Dimitris Maniadakis and Dimitris Varoutas. Fitting planar proximity graphs on real street networks. In Proceedings of ECCS 2014: European Conference on Complex Systems, 11–20. Springer, 2016. doi:10.1007/978-3-319-29228-1_2.
Luke Mathieson and Pablo Moscato. An introduction to proximity graphs. In Pablo Moscato and Natalie Jane de Vries, editors, Business and Consumer Analytics: New Ideas, pages 213–233. Springer, 2019. doi:10.1007/978-3-030-06222-4_4.
David W Matula and Robert R Sokal. Properties of gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geographical Analysis, 12(3):205–222, 1980. doi:10.1111/j.1538-4632.1980.tb00031.x.
Joseph S B Mitchell and Wolfgang Mulzer. Proximity algorithms. In Jacob E Goodman, Joseph O'Rourke, and Tóth Csaba D, editors, Handbook of Discrete Computational Geometry, pages 849–874. CRC Press, 3 edition, 2018. doi:10.1201/9781315119601-32.
Toshihiro Osaragi and Yuko Hiraga. Street network created by proximity graphs: its topological structure and travel efficiency. In 17th Conference of the Association of Geographic Information Laboratories for Europe on Geographic Information Science (AGILE2014), 1–6. 2014. URL: https://agile-online.org/images/conferences/2014/documents/agile2014_83.pdf.
Joon C Park, Hayong Shin, and Byoung K Choi. Elliptic gabriel graph for finding neighbors in a point set and its application to normal vector estimation. Computer-Aided Design, 38(6):619–626, 2006. doi:10.1016/j.cad.2006.02.008.
John D Radke. On the shape of a set of points. In Godfried T Toussaint, editor, Computational Morphology. A Computational Geometric Approach to the Analysis of Form, volume 6, pages 105–136. Elsevier Science, 1988. doi:10.1016/B978-0-444-70467-2.50014-X.
Atsushi Tero, Shigeru Takagi, Tetsu Saigusa, Katsuya Ito, Daniel P. Bebber, Mark D. Fricker, Kenji Yumiki, Ryo Kobayashi, and Toshiyuki Nakagaki. Rules for biologically inspired adaptive network design. Science, 327(5964):439–442, 2010. doi:10.1126/science.1177894.
Godfried T Toussaint. A graph-theoretical primal sketch. In Godfried T Toussaint, editor, Computational Morphology. A Computational Geometric Approach to the Analysis of Form, volume 6, pages 229–260. Elsevier Science, 1988. doi:10.1016/B978-0-444-70467-2.50019-9.
Godfried T Toussaint. Applications of the relative neighbourhood graph. International Journal of Advances in Computer Science & Its Applications, 4(3):77–85, 2014. URL: http://journals.theired.org/journals/paper/details/4323.html.
Godfried T Toussaint. The sphere of influence graph: theory and applications. International Journal of Information Technology & Computer Science, 14(2):37–42, 2014. URL: https://studylib.net/doc/18368340/the-sphere-of-influence-graph--theory-and-applications.
Godfried T. Toussaint. The relative neighbourhood graph of a finite planar set. Pattern Recognition, 12(4):261–268, 1980. doi:10.1016/0031-3203(80)90066-7.
Remco C. Veltkamp. The γ-neighborhood graph. Computational Geometry, 1(4):227–246, 1992. doi:10.1016/0925-7721(92)90003-B.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, and others. SciPy 1.0: fundamental algorithms for scientific computing in python. Nature Methods, 17:261–272, 2020. doi:10.1038/s41592-019-0686-2.
Daisuke Watanabe. A study on analyzing the grid road network patterns using relative neighborhood graph. In The Ninth International Symposium on Operations Research and Its Applications, 112–119. Lecture Notes in Operations Research. Beijing, China: World Publishing …, 2010. URL: https://www.aporc.org/LNOR/10/ISORA2010F11.pdf.
Jianhua Yang, Vladimir Estivill-Castro, and Stephan K Chalup. Support vector clustering through proximity graph modelling. In Proceedings of the 9th International Conference on Neural Information Processing, 2002. ICONIP'02., volume 2, 898–903. IEEE, 2002. doi:10.1109/ICONIP.2002.1198191.
Richard Zemel and Miguel Carreira-Perpiñán. Proximity graphs for clustering and manifold learning. In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 17, 225–232. MIT Press, 2004. URL: https://proceedings.neurips.cc/paper_files/paper/2004/file/dcda54e29207294d8e7e1b537338b1c0-Paper.pdf.