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

DOI10.1016/S0925-7721(02)00102-5MaRDI QIDQ1869747zbMATHWikidataFDO

Authors Prosenjit Bose, Anil Maheshwari, Pat Morin

Publication date 28 April 2003

Published in Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

clusteringrandomizationquadtreealgorithmdata structurefacility locationgeometric optimizationFermat-Weber centerrange tree

Mathematics Subject Classification ID

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

Recommendations

• On the Continuous Fermat-Weber Problem
• On the Fermat-Weber center of a convex object
• \((1 + \varepsilon)\)-approximation for facility location in data streams
• scientific article; zbMATH DE number 510764
• Clustering to minimize the maximum intercluster distance

Cites work

• scientific article; zbMATH DE number 2185624 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3401212 (Why is no real title available?)
• Algebraic optimization: The Fermat-Weber location problem
• Efficient Algorithms for the Capacitated 1-Median Problem
• Finding Groups in Data
• Improved algorithms for placing undesirable facilities
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Robust distance-based clustering with applications to spatial data mining
• Sublinear time algorithms for metric space problems
• The algebraic degree of geometric optimization problems
• The complexity of facets (and some facets of complexity)
• The rectilinear distance minisum problem with minimum distance constraints:
• Two Notes on Notation

Cited in

(26)

• Geometric median and robust estimation in Banach spaces
• Deterministic metric 1-median selection with very few queries
• Finding all pure strategy Nash equilibria in a planar location game
• Improved upper bounds for the Steiner ratio
• Two proximal splitting methods in Hadamard spaces
• Single facility collection depots location problem in the plane
• On Combinatorial Depth Measures
• Fast Summation by Interval Clustering for an Evolution Equation with Memory
• Approximating generalized distance functions on weighted triangulated surfaces with applications
• CONSTRUCTING OPTIMAL HIGHWAYS
• An efficient sum query algorithm for distance-based locally dominating functions
• The optimal solution set of the multi-source Weber problem
• Computing generalized higher-order Voronoi diagrams on triangulated surfaces
• Median problem in some plane triangulations and quadrangulations.
• Robust and scalable Bayes via a median of subset posterior measures
• On the Fermat-Weber center of a convex object
• Improved PTASs for convex barrier coverage
• The projection median of a set of points
• Deterministic metric 1-median selection with A \(1-o(1)\) fraction of points ignored
• Subdivision methods for sum-of-distances problems: Fermat-Weber point, \(n\)-ellipses and the min-sum cluster Voronoi diagram (media exposition)
• On stars and Steiner stars
• Matching point sets with respect to the earth mover's distance
• Approximating the distribution of the median and other robust estimators on uncertain data
• Sensor network topology design and analysis for efficient data gathering by a mobile mule
• Robust \(\ell_1\) approaches to computing the geometric median and principal and independent components
• On the probabilistic behaviour of a heuristic algorithm for maximal Hamiltonian tours

Describes a project that uses

Uses Software

• clusfind

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1869747)