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