An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)

DOI10.1016/0167-6377(95)00025-FzbMath0858.90087MaRDI QIDQ1924622

Emanuel Melachrinoudis, James MacGregor Smith

Publication date: 31 March 1997

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

weighted Voronoi diagramEuclidean weighted maximin problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Discrete location and assignment (90B80)

Related Items

Hazardous waste management problem: the case for incineration ⋮ Computing an obnoxious anchored segment. ⋮ Semi-obnoxious single facility location in Euclidean space. ⋮ A general model for the undesirable single facility location problem ⋮ Undesirable facility location with minimal covering objectives ⋮ Maximin location: Discretization not always works ⋮ The Location of Undesirable Facilities ⋮ Locating two obnoxious facilities using the weighted maximin criterion

Uses Software

• Voronoi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal algorithm for constructing the weighted Voronoi diagram in the plane
• A sweepline algorithm for Voronoi diagrams
• A heuristic approach to the single facility maximin location problem
• A Maxmin Location Problem
• The Voronoi Partition of a Network and Its Implications in Location Theory
• Heuristic and Special Case Algorithms for Dispersion Problems
• A new duality result concerning Voronoi diagrams