We address the following problem: Given two subsets Γ and φ of the plane, find the minimum enclosing circle of Γ whose center is constrained to lie on φ. We first study the case when Γ is a set of n points and φ is either a set of points, a set of segments (lines) or a simple polygon. We propose several algorithms, the first solves the problem when φ is a set of m segments (or m points) in expected Θ((n+m) log ω) time, where ω = min{n,m}. Surprisingly, when φ is a simple m-gon, we can improve the expected running time to Θ(m + n log n). Moreover, if Γ is the set of vertices of a convex n-gon and φ is a simple m-gon, we can solve the problem in expected Θ(n+m) time. We provide matching lower bounds in the algebraic computation tree model for all the algorithms presented in this paper. While proving these results, we obtained a ?(n logm) lower bound for the following problem: Given two sets A and B in R of sizes m and n, respectively, decide if A is a subset of B.

Additional Metadata
Keywords facility location problems, minimum enclosing circle
Persistent URL dx.doi.org/10.1007/978-3-642-54423-1_8
Citation
Barba, L. (Luis), Bose, P, & Langerman, S. (Stefan). (2014). Optimal Algorithms for Constrained 1-Center Problems. doi:10.1007/978-3-642-54423-1_8