In this paper we consider constrained versions of the Euclidean minimax facility location problem. We provide an O(n + m) time algorithm for the problem of constructing the minimum enclosing circle of a set of n points with center constrained to satisfy m linear constraints. As a corollary, we obtain a linear time algorithm for the problem when the center is constrained to lie in an m-vertex convex polygon, which improves the best known solution of O((n + m) log(n + m)) time. We also consider some constrained versions of the maximin problem, namely an obnoxious facility location problem in which we are given a set of n linear constraints, each representing a halfplane where some population may live, and the goal is to locate a point such that the minimum distance to the inhabited region is maximized. We provide optimal Θ(n) time algorithms for this problem in the plane, as well as on the sphere.
