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

quadtree; algorithm; clustering; randomization; facility location; geometric optimization; data structure; Fermat-Weber center; range tree

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

52B55: Computational aspects related to convexity

90C27: Combinatorial optimization

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

90B80: Discrete location and assignment

68P05: Data structures

Related Items

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

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