Fast approximations for sums of distances, clustering and the Fermat-Weber problem

DOI10.1016/S0925-7721(02)00102-5zbMath1016.65040WikidataQ62065763 ScholiaQ62065763MaRDI QIDQ1869747

Pat Morin, Prosenjit Bose, Anil Maheshwari

Publication date: 28 April 2003

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

quadtreealgorithmclusteringrandomizationfacility locationgeometric optimizationdata structureFermat-Weber centerrange tree

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Computational aspects related to convexity (52B55) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80) Data structures (68P05)

Related Items (22)

On stars and Steiner stars ⋮ Robust \(\ell_1\) approaches to computing the geometric median and principal and independent components ⋮ Improved upper bounds for the Steiner ratio ⋮ The optimal solution set of the multi-source Weber problem ⋮ Two proximal splitting methods in Hadamard spaces ⋮ Approximating generalized distance functions on weighted triangulated surfaces with applications ⋮ Deterministic metric 1-median selection with A \(1-o(1)\) fraction of points ignored ⋮ On the probabilistic behaviour of a heuristic algorithm for maximal Hamiltonian tours ⋮ Median problem in some plane triangulations and quadrangulations. ⋮ On Combinatorial Depth Measures ⋮ Matching point sets with respect to the earth mover's distance ⋮ Improved PTASs for convex barrier coverage ⋮ Sensor network topology design and analysis for efficient data gathering by a mobile mule ⋮ Finding all pure strategy Nash equilibria in a planar location game ⋮ Geometric median and robust estimation in Banach spaces ⋮ Computing generalized higher-order Voronoi diagrams on triangulated surfaces ⋮ CONSTRUCTING OPTIMAL HIGHWAYS ⋮ Unnamed Item ⋮ The projection median of a set of points ⋮ Single facility collection depots location problem in the plane ⋮ Robust and Scalable Bayes via a Median of Subset Posterior Measures ⋮ On the Fermat-Weber center of a convex object

Uses Software

• clusfind

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraic optimization: The Fermat-Weber location problem
• The complexity of facets (and some facets of complexity)
• The algebraic degree of geometric optimization problems
• Improved algorithms for placing undesirable facilities
• Sublinear time algorithms for metric space problems
• Two Notes on Notation
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Finding Groups in Data
• Efficient Algorithms for the Capacitated 1-Median Problem
• The rectilinear distance minisum problem with minimum distance constraints:
• Robust distance-based clustering with applications to spatial data mining

This page was built for publication: Fast approximations for sums of distances, clustering and the Fermat-Weber problem