Iterated nearest neighbors and finding minimal polytopes

DOI10.1007/BF02574012zbMath0807.68094MaRDI QIDQ1327455

Jeff Erickson, David Eppstein

Publication date: 1 March 1995

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

Full work available at URL: https://eudml.org/doc/131305

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

EFFICIENT APPROXIMATION ALGORITHMS FOR TWO-LABEL POINT LABELING, Computing the Smallest T-Shaped Polygon Containing k Points, POINT SET LABELING WITH SPECIFIED POSITIONS, Region-restricted clustering for geographic data mining, Optimal placement of convex polygons to maximize point containment, Offset-polygon annulus placement problems, Geometric applications of posets, Dynamic Euclidean minimum spanning trees and extrema of binary functions, On nearest-neighbor graphs, Faster geometric \(k\)-point MST approximation, Compact location problems, Extending range queries and nearest neighbors, Algorithms for proximity problems in higher dimensions, On finding a large number of 3D points with a small diameter, Covering points with a polygon, Translating a convex polygon to contain a maximum number of points., QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• On a circle placement problem
• The power of geometric duality
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Topologically sweeping an arrangement
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Finding minimum area \(k\)-gons
• Maintaining the minimal distance of a point set in polylogarithmic time
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• On vertical ray shooting in arrangements
• Finding k points with minimum diameter and related problems
• Sets with No Empty Convex 7-Gons
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• An Improved Algorithm for Constructing kth-Order Voronoi Diagrams
• Decomposable searching problems I. Static-to-dynamic transformation
• New Upper Bounds in Klee’s Measure Problem
• SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS
• Slowing down sorting networks to obtain faster sorting algorithms
• Static and dynamic algorithms for k-point clustering problems