Approximation algorithms for geometric problems

Marshall Wayne Bern and David Eppstein
Approximation Algorithms for NP-hard Problems, Dorit Hochbaum, ed., PWS Publishing, 1996, pp. 296–345

Cited by:

• Polynomial time approximation schemes for Euclidean TSP and other geometric problems
• New approximation algorithms for the Steiner tree problems
• Efficient algorithms for geometric optimization
• Incremental clustering and dynamic information retrieval
• Average-case ray shooting and minimum weight triangulations
• Shortest paths and networks
• Nearly linear time approximation schemes for Euclidean TSP and other geometric problems
• Progress in Hierarchical Clustering & Minimum Weight Triangulation
• The dynamic servers problem
• Compact Location Problems
• Quasi-greedy triangulations approximating the minimum weight triangulation
• Point set labeling with sliding labels
• Segmentation problems
• Approximation schemes for Euclidean $k$-medians and related problems
• Subexponential-time algorithms for minimum-weight triangulation and related problems
• The $k$-Steiner ratio in the rectilinear plane
• A randomized approximation scheme for metric MAX-CUT
• Low energy and mutually distant sampling
• Clustering in large graphs and matrices
• Approximating minimum-weight triangulations in three dimensions
• Geometric shortest paths and network optimization
• Clustering for edge-cost minimization
• Polynomial time approximation schemes for geometric $k$-clustering
• Approximation of geometric dispersion problems
• Projective clustering in high dimensions using core-sets
• Approximate clustering via core-sets
• Polynomial-time approximation schemes for geometric min-sum median clustering
• Map Labeling Problems
• Smooth kinetic maintenance of clusters
• Euclidean bounded-degree spanning tree ratios
• Polynomial-time approximation schemes for metric min-sum median clustering
• An impossibility theorem for clustering
• Improved approximation of maximum planar subgraph
• Clustering motion
• Covering with ellipses
• Geometric Problems in Cartographic Networks
• NP-completeness column 24
• Minimum-weight triangulation is NP-hard