Algorithms for proximity problems in higher dimensions

DOI10.1016/0925-7721(95)00009-7zbMath0855.68110OpenAlexW2022853835MaRDI QIDQ1917037

Matthew T. Dickerson, David Eppstein

Publication date: 14 January 1997

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(95)00009-7

zbMATH Keywords

Delaynay triangulation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Related Items (9)

Kinetic \(k\)-semi-Yao graph and its applications ⋮ On nearest-neighbor graphs ⋮ Kinetic Reverse k-Nearest Neighbor Problem ⋮ Geometric Applications of Posets ⋮ Approximate $k$-Nearest Neighbor Graph on Moving Points ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ Geometric applications of posets ⋮ Finding the k Shortest Paths ⋮ Reporting intersections among thick objects.

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Fixed-radius near neighbors search algorithms for points and segments
• An O(n log n) algorithm for the all-nearest-neighbors problem
• L-infinity interdistance selection by parametric search
• Maintaining the minimal distance of a point set in polylogarithmic time
• The complexity of finding fixed-radius near neighbors
• Iterated nearest neighbors and finding minimal polytopes
• Provably good mesh generation
• On nearest-neighbor graphs
• Time bounds for selection
• Selecting distances in the plane
• An optimal algorithm for selection in a min-heap
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• ENUMERATING INTERDISTANCES IN SPACE
• SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS

This page was built for publication: Algorithms for proximity problems in higher dimensions