Abstract
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 + nlogn). 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 ℝ of sizes m and n, respectively, decide if A is a subset of B.
Research supported in part by NSERC.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aggarwal, A., Guibas, L., Saxe, J., Shor, P.: A linear time algorithm for computing the Voronoi diagram of a convex polygon. In: Proceedings of STOC, pp. 39–45. ACM, New York (1987)
Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proceedings of STOC, pp. 80–86. ACM, New York (1983)
Bose, P., Langerman, S., Roy, S.: Smallest enclosing circle centered on a query line segment. In: Proceedings of CCCG, pp. 167–170 (2008)
Bose, P., Toussaint, G.: Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications. In: Proceedings of CGI, pp. 102–111 (1996)
Bose, P., Wang, Q.: Facility location constrained to a polygonal domain. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 153–164. Springer, Heidelberg (2002)
Chan, T.M.: Geometric applications of a randomized optimization technique. Discrete and Computational Geometry 22, 547–567 (1999)
Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M.: Diameter, width, closest line pair, and parametric searching. DCG 10, 183–196 (1993)
Hurtado, F., Sacristan, V., Toussaint, G.: Some constrained minimax and maximim location problems. Studies in Locational Analysis 15, 17–35 (2000)
Joe, B., Simpson, R.B.: Corrections to Lee’s visibility polygon algorithm. BIT Numerical Mathematics 27, 458–473 (1987)
Lee, D.T.: Farthest neighbor Voronoi diagrams and applications. Report 80-11-FC-04, Dept. Elect. Engrg. Comput. Sci. (1980)
Lee, D.T.: On finding the convex hull of a simple polygon. International Journal of Parallel Programming 12(2), 87–98 (1983)
Matousek, J.: Computing the center of planar point sets. Discrete and Computational Geometry 6, 221 (1991)
Matoušek, J.: Construction of epsilon nets. In: Proceedings of SCG, pp. 1–10. ACM, New York (1989)
Megiddo, N.: Linear-time algorithms for linear programming in ℝ3 and related problems. SIAM J. Comput. 12(4), 759–776 (1983)
Preparata, F.: Minimum spanning circle. In: Preparata, F.P. (ed.) Steps in Computational Geometry. University of Illinois (1977)
Shamos, M., Hoey, D.: Closest-point problems. In: Proceedings of FOCS, pp. 151–162. IEEE Computer Society, Washington, DC (1975)
Sylvester, J.J.: A Question in the Geometry of Situation. Quarterly Journal of Pure and Applied Mathematics 1 (1857)
Yao, A.C.-C.: Decision tree complexity and Betti numbers. In: Proceedings of STOC, pp. 615–624. ACM, New York (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barba, L., Bose, P., Langerman, S. (2014). Optimal Algorithms for Constrained 1-Center Problems. In: Pardo, A., Viola, A. (eds) LATIN 2014: Theoretical Informatics. LATIN 2014. Lecture Notes in Computer Science, vol 8392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54423-1_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-54423-1_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54422-4
Online ISBN: 978-3-642-54423-1
eBook Packages: Computer ScienceComputer Science (R0)