20140101
Optimal Algorithms for Constrained 1Center Problems
Publication
Publication
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 mgon, we can improve the expected running time to Θ(m + n log n). Moreover, if Γ is the set of vertices of a convex ngon and φ is a simple mgon, 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/9783642544231_8 
Citation 
Barba, L. (Luis), Bose, P, & Langerman, S. (Stefan). (2014). Optimal Algorithms for Constrained 1Center Problems. doi:10.1007/9783642544231_8
