On nearest-neighbor graphs

DOI10.1007/PL00009293zbMath0874.60014OpenAlexW2072596762WikidataQ61645302 ScholiaQ61645302MaRDI QIDQ1355198

O. Diekmann

Publication date: 19 May 1997

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/pl00009293

zbMATH Keywords

clustering analysisgeometric embedding problemsprobabilistic properties of the \(k\)-nearest-neighbors graph

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05)

Related Items (22)

Weak laws of large numbers in geometric probability ⋮ Continuous amortization and extensions: with applications to bisection-based root isolation ⋮ Multi-dimensional Kronecker sequences with a small number of gap lengths ⋮ PROXIMITY GRAPHS: E, δ, Δ, χ AND ω ⋮ Algorithms for proximity problems in higher dimensions ⋮ The rectangle of influence drawability problem ⋮ Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers ⋮ Discussion about properties of first nearest neighbor graphs ⋮ On the number of weakly connected subdigraphs in random \(k\)NN digraphs ⋮ Local properties of geometric graphs ⋮ \(k\)-nearest-neighbor clustering and percolation theory ⋮ Markov incremental constructions ⋮ Ranking inter-relationships between clusters ⋮ From approximate factorization to root isolation with application to cylindrical algebraic decomposition ⋮ Sigma-local graphs ⋮ On the Number of Reflexive and Shared Nearest Neighbor Pairs in One-Dimensional Uniform Data ⋮ Extension of one-dimensional proximity regions to higher dimensions ⋮ Empty region graphs ⋮ Unnamed Item ⋮ Simulated Annealing and Genetic Algorithms in Quest of Optimal Triangulations ⋮ A classification of isomorphism-invariant random digraphs ⋮ A worst-case bound for topology computation of algebraic curves

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two probabilistic results on rectilinear Steiner trees
• The expected size of some graphs in computational geometry
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Transitions in geometric minimum spanning trees
• Iterated nearest neighbors and finding minimal polytopes
• A vectorized near neighbors algorithm of order N using a monotonic logical grid
• Algorithms for proximity problems in higher dimensions
• The realization problem for Euclidean minimum spanning trees is NP-hard
• \(k\)-nearest-neighbor clustering and percolation theory
• On nearest-neighbor graphs

This page was built for publication: On nearest-neighbor graphs