Geometric complexity of some location problems
type: Item
instance of: scholarly article
title: Geometric complexity of some location problems
zbMATH Open document ID: 0639.68038
DOI: 10.1007/BF01840442
author: B. George
published in: Algorithmica
publication date: 1986-01-01T00:00:00Z
review text: Given a set of n demand points with weight \(w_ i\), \(i=1,2,...,n\), in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An \(\Omega\) (n log n) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4043243
zbMATH Keywords: maximum gap
zbMATH Keywords: computational geometry
zbMATH Keywords: location problems
zbMATH Keywords: 1-line center
zbMATH Keywords: lower bound
MaRDI profile type: Publication
cites work: Q4091421
cites work: On the complexity of computations under varying sets of primitives
cites work: Optimal Point Location in a Monotone Subdivision
cites work: On the complexity of computing the measure of ∪[a i ,b i ]
cites work: An efficient algorithm for determining the convex hull of a finite planar set
cites work: Optimal Search in Planar Subdivisions
cites work: The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
cites work: Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
cites work: On the complexity of locating linear facilities in the plane
cites work: Linear facility location. Solving extensions of the basic problem
cites work: A Note on Locating a Set of Points in a Planar Subdivision
cites work: Convex hulls of finite sets of points in two and three dimensions
cites work: On the Optimality of Some Set Algorithms
full work available at URL: https://doi.org/10.1007/bf01840442
OpenAlex ID: W1998932824
Recommended article: Q4728245
Recommended article: On the Complexity of Some Common Geometric Location Problems
Recommended article: Technical Note—On the Complexity of Some Classes of Location Problems
Recommended article: A study on two geometric location problems
Recommended article: The geometry of optimal partitions in location problems
Recommended article: Parameterized Complexity of Geodetic Set
Recommended article: On the Complexity of Some Geometric Problems With Fixed Parameters
Recommended article: Geometric methods to solve max-ordering location problems
description: scientific article; zbMATH DE number 4043243