On the Continuous Fermat-Weber Problem

We give the firstexact algorithmic study of facility location problems that deal with finding a median for acontinuum of demand points. In particular, we consider versions of the "continuousk-median (Fermat-Weber) problem" where the goal is to select one or more center points that minimize the average distance to a set of points in a demandregion. In such problems, the average is computed as an integral over the relevant region, versus the usual discrete sum of distances. The resulting facility location problems are inherently geometric, requiring analysis techniques of computational geometry. We provide polynomial-time algorithms for various versions of theL1 1-median (Fermat-Weber) problem. We also consider the multiple-center version of theL1k-median problem, which we prove is NP-hard for largek.

• Publication year

  2003

• Venue

  Operational Research

• Publication date

  2003-10-15

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1287/opre.1040.0137arXiv cs/0310027
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computing the geodesic center of a simple polygon

  2011cited by this paper
• The slab dividing approach to solve the EuclideanP-Center problem

  2005cited by this paper
• Shortest Paths and Networks

  2004cited by this paper
• The one-round Voronoi game replayed

  2003cited by this paper
• Finding a Region with the Minimum Total L 1 Distance from Prescribed Terminals

  2003cited by this paper
• Finding a Region with the Minimum Total L1 Distance from Prescribed Terminals

  2003cited by this paper
• Geometric Shortest Paths and Network Optimization

  2000cited by this paper
• On Minimum Stars and Maximum Matchings

  2000cited by this paper
• The Capacitated K-Center Problem

  2000cited by this paper
• On minimum stars, minimum Steiner stars, and maximum matchings

  1999cited by this paper
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane

  1999cited by this paper
• More planar two-center algorithms

  1999cited by this paper
• Two-point Euclidean shortest path queries in the plane

  1999influential reference
• Classification of Location Problems

  1999cited by this paper
• Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles

  1998cited by this paper
• The Weber problem with regional demand

  1998cited by this paper
• Classification of location models

  1998cited by this paper
• Location and shape of a rectangular facility in R n : convexity properties

  1998cited by this paper
• Location and shape of a rectangular facility in ℝn. Convexity properties. Convexity properties

  1998cited by this paper
• Faster construction of planar two-centers

  1997cited by this paper
• The Discrete 2-Center Problem

  1997cited by this paper
• Facility location: a survey of applications and methods

  1996cited by this paper
• A Near-Linear Algorithm for the Planar 2-Center Problem

  1996cited by this paper
• A Multifacility Location Problem on Median Spaces

  1996cited by this paper
• Rectilinear and polygonal p-piercing and p-center problems

  1996cited by this paper
• Facility Location: A Survey of Applications and Methods

  1996cited by this paper
• Replacing Discrete Demand with Continuous Demand

  1995cited by this paper
• An optimal algorithm for finding segments intersections

  1995cited by this paper
• Continuous Location Problems

  1995cited by this paper
• On the Set of Optimal Points to the Weber Problem: Further Results

  1994cited by this paper
• Technical Note - Algorithms for Weber Facility Location in the Presence of Forbidden Regions and/or Barriers to Travel

  1994cited by this paper
• THE WEBER PROBLEM: HISTORY AND PERSPECTIVES.

  1993cited by this paper
• A Faster Algorithm for the Two-Center Decision Problem

  1993cited by this paper
• The conditional p‐center problem in the plane

  1993cited by this paper
• L1 shortest paths among polygonal obstacles in the plane

  1992cited by this paper
• Linear Time Algorithms for the Weighted Tailored 2-Partition Problem and the Weighted 2-Center Problem under linfty-Distance

  1992cited by this paper
• Discrete Location Theory

  1991cited by this paper
• A new algorithm for shortest paths among obstacles in the plane

  1991cited by this paper
• Discrete location theory

  1991cited by this paper
• Triangulating a simple polygon in linear time

  1990cited by this paper
• An optimal approximation algorithm for the rectilinearm-center problem

  1990cited by this paper
• Algebraic optimization: The Fermat-Weber location problem

  1990cited by this paper
• Locating Facilities on the Manhattan Metric with Arbitrarily Shaped Barriers and Convex Forbidden Regions

  1989cited by this paper
• An overview of representative problems in location research

  1989cited by this paper
• NP-Hard, Capacitated, Balanced p-Median Problems on a Chain Graph with a Continuum of Link Demands

  1988cited by this paper
• An optimal algorithm for intersecting line segments in the plane

  1988cited by this paper
• The algebraic degree of geometric optimization problems

  1988cited by this paper
• On the rectangular p‐center problem

  1987cited by this paper
• On the Solution Value of the Continuous p-Center Location Problem on a Graph

  1987cited by this paper
• An O(n log n) Randomizing Algorithm for the Weighted Euclidean 1-Center Problem

  1986cited by this paper
• Rectilinear planar layouts and bipolar orientations of planar graphs

  1986cited by this paper
• A Best Possible Heuristic for the k-Center Problem

  1985cited by this paper
• Probabilistic analysis of geometric location problems

  1984cited by this paper
• The Weighted Euclidean 1-Center Problem

  1983cited by this paper
• Facility Locations with the Manhattan Metric in the Presence of Barriers to Travel

  1983cited by this paper
• New Results on the Complexity of p-Center Problems

  1983cited by this paper
• Planar Formulae and Their Uses

  1982cited by this paper
• Worst-Case and Probabilistic Analysis of a Geometric Location Problem

  1981cited by this paper
• Technical Note - Equivalence between the Direct Search Approach and the Cut Approach to the Rectilinear Distance Location Problem

  1981cited by this paper
• Optimal location of a facility relative to area demands

  1980influential reference
• An Algorithmic Approach to Network Location Problems. II: The p-Medians

  1979cited by this paper
• An Algorithmic Approach to Network Location Problems. I: The p-Centers

  1979cited by this paper
• AN ALGORITHMIC APPROACH TO NETWORK LOCATION PROBLEMS.

  1979cited by this paper
• A Nonlinear Approximation Method for Solving a Generalized Rectangular Distance Weber Problem

  1972cited by this paper
• Technical Note - The Optimal Location of New Facilities Using Rectangular Distances

  1971cited by this paper
• Optimal Center Location in Simple Networks

  1971cited by this paper
• Location of facilities with rectangular distances among point and area destinations

  1971influential reference

• Locational Decision-Making and Representational Impacts

  2025cites this paper
• Scales of Fr\'echet means and Karcher quasi-arithmetic means

  2025cites this paper
• Structural and Solution Analysis for the Ordered Weber Problem under Spatial Uncertainty

  2025cites this paper
• Sensor placement via large deviations in the Eikonal equation

  2025cites this paper
• Fixed Topology Minimum-Length Trees with Neighborhoods: A Steiner tree based approach

  2025cites this paper
• Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares

  2025cites this paper
• On the Complexity of p-Order Cone Programs

  2025cites this paper
• On the location of geometrical medians of triangles

  2024cites this paper
• Reviewing extensions and solution methods of the planar Weber single facility location problem

  2024cites this paper
• Fixed Topology Minimum-Length Trees with Neighborhoods

  2024cites this paper
• Optimized Operation Methods of the Wafer Surface Defect Detection

  2024cites this paper
• Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares

  2024cites this paper
• Continuous approximation formulas for location problems

  2022cites this paper
• An Optimized Discrete Data Classification Method in <math xmlns="http://www.w3.org/1998/Math/MathML" id="M1"> <mi>N</mi> </math>-Dimensional

  2022cites this paper
• An Optimized Discrete Data Classification Method in N -Dimensional

  2022cites this paper
• Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram (Media Exposition)

  2022cites this paper
• Computational Optimized Monitoring Methodology to Avoid Crowd Crush Accidents with Scattered Data

  2022cites this paper
• A branch-and-price approach for the continuous multifacility monotone ordered median problem

  2021cites this paper
• Conditional facility location problems with continuous demand and a polygonal barrier

  2021cites this paper
• Certified Approximation Algorithms for the Fermat Point and n-Ellipses

  2021cites this paper
• Reliable Intensity Vector Selection for Multi-Source Direction-of-Arrival Estimation Using a Single Acoustic Vector Sensor

  2021cites this paper
• Location problems with continuous demand and unreliable facilities: Applications of families of incremental Voronoi diagrams

  2021cites this paper
• Continuous facility location on graphs

  2020cites this paper
• Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case

  2020cites this paper
• Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings

  2020cites this paper
• A Spatial Optimization Approach for Solving a Multi-facility Location Problem with Continuously Distributed Demand

  2020cites this paper
• Memoryless Sequences for General Losses

  2020cites this paper
• Algorithm for Two-Phase Facility Planning via Balanced Clustering and Integer Programming

  2020cites this paper
• Competitive location problems: balanced facility location and the One-Round Manhattan Voronoi Game

  2020cites this paper
• Certified Approximation Algorithms for the Fermat Point

  2020cites this paper
• Anti-covering Problems

  2019cites this paper
• Optimal Configurations in Coverage Control with Polynomial Costs

  2018cites this paper
• Petri Varvia UNCERTAINTY QUANTIFICATION IN REMOTE SENSING OF FORESTS

  2018cites this paper
• On the geometric median of triangular domains and other median type points

  2018cites this paper
• Semi-discrete optimal transport - the case p=1

  2017cites this paper
• A polynomial-time algorithm for the discrete facility location problem with limited distances and capacity constraints

  2017cites this paper
• Competition and spatial efficiency

  2017cites this paper
• Some remarks on an efficient algorithm to find a centroid in a k-dimensional real space

  2016cites this paper
• A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand

  2016cites this paper
• A geographic optimization approach to coast guard ship basing

  2015cites this paper
• Structural Properties of Voronoi Diagrams in Facility Location Problems with Continuous Demand

  2015cites this paper
• The Wisdom of Multiple Guesses

  2015cites this paper
• Serving regional demand in facility location

  2014cites this paper
• An Approximation Algorithm for the Continuous k-Medians Problem in a Convex Polygon

  2014cites this paper
• Retail Store Density and the Cost of Greenhouse Gas Emissions

  2014cites this paper
• A generalized Weber problem with different gauges for different regions

  2014cites this paper
• On the continuous Fermat-Weber problem for a convex polygon using Euclidean distance

  2014cites this paper
• Dividing a Territory Among Several Facilities

  2013cites this paper
• Problem Transformation

  2013cites this paper
• Continuous surface representation and approximation: spatial analytical implications

  2013cites this paper
• Adaptive Deployment of Mobile Robotic Networks

  2013cites this paper
• Asymptotic optimal location of facilities in a competition between population and industries

  2013cites this paper
• Revisiting the Optimal Center Location. A Spatial Thinking Based on Robustness, Sensitivity, and Influence Analysis

  2013cites this paper
• Théorie des jeux et apprentissage pour les réseaux sans fil distribués

  2013cites this paper
• Balancing workloads of service vehicles over a geographic territory

  2013cites this paper
• On the Weber facility location problem with limited distances and side constraints

  2012cites this paper
• Random Search Algorithm for the Generalized Weber Problem

  2012cites this paper
• ADAPTATION OF THE PROBABILITY CHANGING METHOD FOR WEBER PROBLEM WITH AN ARBITRARY METRIC

  2012cites this paper
• Equitable partitioning with obstacles

  2012cites this paper
• Algorithm for Approximate Solution of the Generalized Weber Problem with an Arbitrary Metric

  2012cites this paper
• Analytical framework for recurrence network analysis of time series.

  2012cites this paper
• Supply Chain Design and the Cost of Greenhouse Gas Emissions

  2012cites this paper
• The Projection Median of a Set of Points in ℝd

  2012cites this paper
• On the Weber facility location problem with limited distances and side constraints

  2011cites this paper
• A multi-dimensional shooting algorithm for the two-facility location-allocation problem with dense demand

  2011cites this paper
• Extended grassfire transform on medial axes of 2D shapes

  2011cites this paper
• More about base station location games

  2011cites this paper
• Sensor-based robot deployment algorithms

  2010cites this paper
• Vehicle placement to intercept moving targets

  2010cites this paper
• Adaptive Algorithms for Coverage Control and Space Partitioning in Mobile Robotic Networks

  2010cites this paper
• Integer Point Sets Minimizing Average Pairwise l1 Distance: What is the Optimal Shape of a Town?

  2010cites this paper
• Algorithms for Packing Problems

  2010cites this paper
• Integer point sets minimizing average pairwise L[subscript 1] distance: What is the optimal shape of a town?

  2010cites this paper
• Maximising coverage of spatial demand for service

  2009cites this paper
• The Projection Median of a Set of Points in R2

  2009cites this paper
• Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms

  2009cites this paper
• Impact of the Norm on Optimal Locations

  2009cites this paper
• Distributed Control of Robotic Networks

  2009cites this paper
• Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance

  2009cites this paper
• Facility Location Optimization via Multi-Agent Robotic Systems

  2008cites this paper
• A continuous analysis framework for the solution of location-allocation problems with dense demand

  2008cites this paper
• An efficient solution method for Weber problems with barriers based on genetic algorithms

  2007cites this paper
• Continuous space facility location for covering spatial demand objects

  2007cites this paper
• Weber problems with mixed distances and regional demand

  2007cites this paper
• Minimum-Cost Load-Balancing Partitions

  2006cites this paper
• Geometric facility location under continuous motion: bounded-velocity approximations to the mobile euclidean k-centre and k-median problems

  2006cites this paper
• The 1-Median And 1-Antimedian Problems With Continuous Probabilistic Demand Weights

  2006cites this paper
• Inventory pre-positioning for humanitarian operations

  2006cites this paper
• Median and Related Local Filters for Tensor-Valued Images

  2005cites this paper
• Matrix-Valued Filters as Convex Programs

  2005cites this paper
• Concepção Híbrida de Otimização por Nuvem de Partículas Aplicada ao Problema de Weber

  2005cites this paper
• Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices

  2004cites this paper
• Universität Des Saarlandes Fachrichtung 6.1 – Mathematik Median and Related Local Filters for Tensor-valued Images Median and Related Local Filters for Tensor-valued Images

  year unknowncites this paper
• The Geometry of Mass Distributions

  year unknowncites this paper