1-Segment Center Problems

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⁴ 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.