1-Segment Center Problems
Hiroshi Imai, D. T. Lee, Chung-Do Yang
ORSA Journal on Computing · 1992 · Volume 4 · Issue 4
Abstract
We consider a minimax facility location problem for n points such that the facility is a line segment of a given length. The general problem can be solved by case analysis in O ( n 4 log n ) time. When the orientation of the segment is fixed, the problem is shown to be linear-time solvable by using the prune-and-search technique. Other variations of this problem are also discussed. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Keywords
facilities/equipment planning, discrete facility location, analysis of algorithms: computational complexity, computational geometry: geometric location, minimax optimization, computational geometry, geometric facility location, minimax optimization
Enable JavaScript for citation tools and additional paper interactions.