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

DOI10.1016/S0925-7721(02)00102-5zbMATH Open1016.65040WikidataQ62065763 ScholiaQ62065763MaRDI QIDQ1869747FDOQ1869747

Pat Morin, Prosenjit Bose, Anil Maheshwari

Publication date: 28 April 2003

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

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

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)

Cites Work

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

Cited In (24)

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

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)