Abstract
The “nearest-neighbor” relation, or more generally the “k-nearest-neighbors” relation, defined for a set of points in a metric space, has found many uses in computational geometry and clustering analysis, yet surprisingly little is known about some of its basic properties. In this paper we consider some natural questions that are motivated by geometric embedding problems. We derive bounds on the relationship between size and depth for the components of a nearest-neighbor graph and prove some probabilistic properties of the k-nearest-neighbors graph for a random set of points.
Article PDF
Similar content being viewed by others
References
N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interscience, New York, 1992.
M. Bern. Two probabilistic results on rectilinear Steiner trees. Algorithmica 3 (1988), 191–204.
J. Boris. A vectorized “near neighbors” algorithm of order N using a monotonic logical grid. Journal of Computational Physics 66 (1986), 1–20.
P. B. Callahan. Optimal parallel all-nearest-neighbors using the well-separated pair decomposition. Proc. 34 th IEEE Symp. on Foundations of Computer Science (1993), pp. 332–340.
P. B. Callahan and S. R. Kosaraju. A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields. Proc. 24th ACM Symp. on Theory of Computing (1992), pp. 546–556.
K. L. Clarkson. Fast algorithms for the all-nearest-neighbors problem. Proc. 24th IEEE Symp. on Foundations of Computer Science (1983), pp. 226–232.
J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups. Springer-Verlag, New York, 1988.
L. Devroye. The expected size of some graphs in computational geometry. Computers & Mathematics with Applications 15 (1988), 53–64.
M. T. Dickerson and D. Eppstein. Algorithms for proximity problems in higher dimensions. Computational Geometry, Theory & Applications 5 (1996), 277–291.
P. Eades and S. Whitesides. The realization problem for Euclidean minimum spanning trees is NP-hard. Proc. 10th ACM Symp. on Computational Geometry (1994), pp. 49–56.
H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987.
D. Eppstein and J. Erickson. Iterated nearest neighbors and finding minimal polytopes. Discrete & Computational Geometry 11 (1994), 321–350.
C. Monma and S. Suri. Transitions in geometric spanning trees. Proc. 7th ACM Symp. on Computational Geometry (1991), pp. 239–249.
M. S. Paterson and F. F. Yao. On nearest-neighbor graphs. Proc. 19th Internat. Coll. on Automata, Languages and Programming. LNCS, 623. Springer-Verlag, Berlin, 1992, pp. 416–426.
S.-H. Teng and F. F. Yao. Percolation and k-nearest neighbor clustering. Manuscript, 1993.
P. Vaidya. An O(n log n) algorithm for the all-nearest-neighbors problem. Discrete & Computational Geometry 4 (1989), 101–115.
Author information
Authors and Affiliations
Corresponding authors
Additional information
D. Eppstein was supported in part by NSF Grant CCR-9258355 and matching funds from the Xerox Corporation. The work of M. S. Paterson was done while this author was visiting Xerox Palo Alto Research Center. He is partially supported by the ESPRIT BRA Program of the EC under Contract 7141 (ALCOMII) and a grant from the Xerox Corporation.
Rights and permissions
About this article
Cite this article
Eppstein, D., Paterson, M.S. & Yao, F.F. On Nearest-Neighbor Graphs. Discrete Comput Geom 17, 263–282 (1997). https://doi.org/10.1007/PL00009293
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/PL00009293