Iterated nearest neighbors and finding minimal polytopes

David Eppstein and Jeffrey Gordon Erickson
Discrete & Computational Geometry 11(3):321–350, Apr 1994
Proc. 4th Symp. Discrete Algorithms, ACM and SIAM, Jan 1993, pp. 64–73
Tech. report 92-71, Univ. of California, Irvine, Dept. of Information and Computer Science, 1992
Mathematical Reviews 95a:68100
Mathematical Reviews 94c:68197
http://www.cs.duke.edu/~jeffe/pubs/small.html

Cited by:

• Translating a convex polygon to contain a maximum number of points
• Static and dynamic algorithms for $k$-point clustering problems
• An $O(n\log n)$ algorithm for finding a $k$-point subset with minimal $L_\infty$-diameter
• On geometric optimization with few violated constraints
• Extending range queries and nearest neighbors
• Optimal placement of convex polygons to maximize point containment
• Spanning trees — short or small
• Enclosing $k$ points in the smallest axis parallel rectangle
• On enclosing $k$ points by a circle
• Efficient parallel algorithms for geometric clustering and partitioning problems
• Map labeling and its generalizations
• Efficient algorithms for geometric optimization
• Separators for sphere-packings and nearest neighbor graphs
• Biased search and $k$-point clustering
• Geometric applications of posets
• Offset-polygon annulus placement problems
• Nearly linear time approximation schemes for Euclidean TSP and other geometric problems
• Geometric applications of a randomized optimization technique
• Polynomial time approximation schemes for Euclidean TSP and other geometric problems
• Closest-point problems in computational geometry
• Finding $k$-closest-pairs efficiently for high dimensional data
• The translation-scale diagram for point-containing placements of a convex polygon
• The anatomy of a geometric algorithm
• Efficient approximation algorithms for multi-label map labeling
• Quantile approximation for robust statistical estimation and kappa-enclosing problems
• Smallest color-spanning objects
• New approximation algorithms for map labeling with sliding labels
• Efficient approximation algorithms for two-label point labeling
• Translating a planar object to maximize point containment
• Shape fitting with outliers
• A simple factor-3 approximation for labeling points with circles
• Minimum area polygons with two reflex angles enclosing $k$ points
• Computing the smallest T-shaped polygon containing $k$ points
• A factor-2 approximation for labeling points with maximum sliding labels
• A note on maximum independent sets in rectangle intersection graphs
• The farthest color Voronoi diagram and related problems
• Space-efficient algorithms for Klee's measure problem
• The translation-scale-rotation diagram for point-containing placements of a convex polygon
• Approximation algorithms for maximum cliques in 3D unit-disk graphs
• Optimal polygon placement