Algorithms for proximity problems in higher dimensions

DOI10.1016/0925-7721(95)00009-7MaRDI QIDQ1917037zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS
• An O(n log n) algorithm for the all-nearest-neighbors problem
• ENUMERATING INTERDISTANCES IN SPACE
• scientific article; zbMATH DE number 437552

Cites work

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

Cited in

(16)

• Geometric applications of posets
• On nearest-neighbor graphs
• Kinetic \(k\)-semi-Yao graph and its applications
• Reporting intersections among thick objects.
• Kinetic reverse \(k\)-nearest neighbor problem
• SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS
• Finding the k Shortest Paths
• Algorithms for computing the optimal transitive approximation of a proximity relation
• Proximity in Arrangements of Algebraic Sets
• On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
• ON ENUMERATING AND SELECTING DISTANCES
• scientific article; zbMATH DE number 2119699 (Why is no real title available?)
• Approximate $k$-Nearest Neighbor Graph on Moving Points
• Geometric applications of posets
• New measures of proximity for the assignment algorithms in the MDVRPTW
• Algorithms for high dimensional stabbing problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1917037)