Iterated nearest neighbors and finding minimal polytopes

DOI10.1007/BF02574012zbMath0807.68094OpenAlexW3137349107MaRDI 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

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

Related Items

Computing the Smallest T-Shaped Polygon Containing k Points, Linear-size universal discretization of geometric center-based problems in fixed dimensions, Cause I'm a genial imprecise point: outlier detection for uncertain data, Enclosing \(k\) points in the smallest axis parallel rectangle, Dynamic Euclidean minimum spanning trees and extrema of binary functions, A new approximation algorithm for labeling points with circle pairs, Approximation and inapproximability results for maximum clique of disc graphs in high dimensions, On nearest-neighbor graphs, On the \(k\)-colored rainbow sets in fixed dimensions, POINT SET LABELING WITH SPECIFIED POSITIONS, The approximation algorithms for a class of multiple-choice problem, An Approximation Algorithm for the Smallest Color-Spanning Circle Problem, Faster geometric \(k\)-point MST approximation, Algorithms for proximity problems in higher dimensions, Computational complexity and approximation for a generalization of the Euclidean problem on the Chebyshev center, Geometric Applications of Posets, Compact location problems, Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set, Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon, Bottleneck convex subsets: finding \(k\) large convex sets in a point set, QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS, On finding a large number of 3D points with a small diameter, GEODESIC DISKS AND CLUSTERING IN A SIMPLE POLYGON, Covering points with a polygon, Translating a convex polygon to contain a maximum number of points., EFFICIENT APPROXIMATION ALGORITHMS FOR TWO-LABEL POINT LABELING, Placing Two Axis-Parallel Squares to Maximize the Number of Enclosed Points, Region-restricted clustering for geographic data mining, Unnamed Item, Smallest \(k\)-enclosing rectangle revisited, Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions, A simple factor-3 approximation for labeling points with circles, Optimal placement of convex polygons to maximize point containment, Smallest k-enclosing rectangle revisited, Algorithms for optimal outlier removal, Offset-polygon annulus placement problems, Offset-polygon annulus placement problems, Geometric applications of posets, A note on maximum independent sets in rectangle intersection graphs, A (slightly) faster algorithm for Klee's measure problem, Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation, Extending range queries and nearest neighbors, Complexity and approximation of the smallest \(k\)-enclosing ball problem

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