Relative neighborhood graphs and their relatives
Authors:
- G.T. ToussaintGTG.T. Toussaint
- 1 September 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the IEEE
- Vol. 80 (9) , 1502-1517
Abstract
Results of neighborhood graphs are surveyed. Properties, bounds on the size, algorithms, and variants of the neighborhood graphs are discussed. Numerous applications including computational morphology, spatial analysis, pattern classification, and databases for computer vision are described.Keywords
This publication has 76 references indexed in Scilit:
- Slimming down by adding; selecting heavily covered points1990
- The expected size of some graphs in computational geometryComputers & Mathematics with Applications, 1988
- Combinatorial complexity bounds for arrangements of curves and surfaces1988
- Filtering Search: A New Approach to Query-AnsweringSIAM Journal on Computing, 1986
- Batched dynamic solutions to decomposable searching problemsJournal of Algorithms, 1985
- New Data Structures for Orthogonal Range QueriesSIAM Journal on Computing, 1985
- Scaling and related techniques for geometry problems1984
- On computing all north-east nearest neighbors in the L1 metricInformation Processing Letters, 1983
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related ProblemsSIAM Journal on Computing, 1982
- On the homogeneous planar Poisson point processMathematical Biosciences, 1970