Abstract
We present anO(n 2 log3 n) algorithm for the two-center problem, in which we are given a setS ofn points in the plane and wish to find two closed disks whose union containsS so that the larger of the two radii is as small as possible. We also give anO(n 2 log5 n) algorithm for solving the two-line-center problem, where we want to find two strips that coverS whose maximum width is as small as possible. The best previous solutions of both problems requireO(n 3) time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
P. Agarwal, B. Aronov, M. Sharir, and S. Suri, Selecting distances in the plane,Algorithmic 9 (1993), 495–514.
P. Agarwal and M. Sharir, Off-line dynamic maintenance of the width of a planar point set,Comput. Geom. Theory Appl. 1 (1991), 65–78.
B. Chazelle, The polygon containment problem, inAdvances in Computer Science, Vol. 1 (F. P. Preparata, ed.), JAI Press, Greenwich, CT, 1983, pp. 1–33.
P. Chew and K. Kedem, Placing the largest similar copy of a convex polygon among polygonal obstacles,Comput. Geom. Theory Appl. 3 (1993), 59–89.
R. Cole, Slowing down sorting networks to obtain faster sorting algorithms,J. Assoc. Comput. Mach. 31 (1984), 200–208.
Z. Drezner, The planar two-center and two-median problems,Transportation Sci. 18 (1984), 351–361.
T. Feder and D. H. Greene, Optimal algorithms for approximate clustering,Proc. 20th ACM Symp. on Theory of Computing, 1988, pp. 434–444.
J. Hershberger and S. Suri, Finding tailored partitions,J. Algorithms 12 (1991), 431–463.
D. T. Lee and Y. Wu, Geometric complexity of some location problems,Algorithmica 1 (1986), 193–211.
N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms,J. Assoc. Comput. Mach. 30 (1983), 852–865.
N. Megiddo, Linear-time algorithms for linear programming in ℝ3 and related problems,SIAM J. Comput. 12 (1983), 759–776.
S. G. Mentzer, Lower bounds on metrick-center problems, Manuscript, 1988.
N. Megiddo and K. Supowit, On the complexity of some common geometric location problems,SIAM J. Comput. 13 (1984), 182–196.
Author information
Authors and Affiliations
Additional information
Communicated by Bernard Chazelle.
Pankaj Agarwal has been supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), an NSF Science and Technology Center, under Grant STC-88-09648. Micha Sharir has been supported by the Office of Naval Research under Grants N00014-89-J-3042 and N00014-90-J-1284, by the National Science Foundation under Grant CCR-89-01484, by DIMACS, and by grants from the US-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. A preliminary version of this paper has appeared inProceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, 1991, pp. 449–458.
Rights and permissions
About this article
Cite this article
Agarwal, P.K., Sharir, M. Planar geometric location problems. Algorithmica 11, 185–195 (1994). https://doi.org/10.1007/BF01182774
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01182774