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 (43)

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

This page was built for publication: Iterated nearest neighbors and finding minimal polytopes