A near-linear algorithm for the planar 2-center problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A near-linear algorithm for the planar 2-center problem

Full text

Pdf (676 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twelfth annual symposium on Computational geometry table of contents

Philadelphia, Pennsylvania, United States

Pages: 106 - 112

Year of Publication: 1996

ISBN:0-89791-804-5

Author

Micha Sharir

School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 23, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237218.237251 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. Agarwal and M. Sharir, Planar geometric location problems, Algomihm~ca 11 (1994), 185-195.
	2	Z. Drezner, The planar two-center and two-median problems, Transportation Science t8 (1984), 351-361.
	3	A. Efrat, A simple algorithm for maintaining the center of a planar point set, M.Sc. Dissertation, The Technion, 1993.
	4	D. Eppstein, Dynamic three-dimensional linear programming, ORSA J. Computing 4 (1992), 360-368.
	5	D. Eppstein, Faster construction of planar twocenters, manuscript~ 1996.
	6	John Hershberger, A faster algorithm for the two-center decision problem, Information Processing Letters, v.47 n.1, p.23-29, Aug. 9, 1993 [doi>10.1016/0020-0190(93)90153-Z]
	7	John Hershberger , Subhash Suri, Finding tailored partitions, Journal of Algorithms, v.12 n.3, p.431-463, Sept. 1991 [doi>10.1016/0196-6774(91)90013-O]
	8	R.Z. Hwang, R.C.T. Lee and R.C. Chang, The slab dividing approach to solve the euclidean P-center problem~ Algor~thmzca 9 (1993), 1-22.
	9	Jerzy W. Jaromczyk , Mirosław Kowaluk, An efficient algorithm for the Euclidean two-center problem, Proceedings of the tenth annual symposium on Computational geometry, p.303-311, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178038]
	10	Matthew J. Katz , Micha Sharir, An expander-based approach to geometric optimization, Proceedings of the ninth annual symposium on Computational geometry, p.198-207, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161137]
	11	M. Overmars and J. van Leeuwen, Maintenance of configurations in the plane. J. Uomp. System $cze, ces 23 ( 1981 ). 166-204.
	12	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	13	N. Megiddo, Linear-time algorithms for linear programmingin R3 and related problems. SIAM J. Coinput. 12 (1983), 759-776.
	14	N. Megiddo and K. Supowit, On the complexity of some common geometric location problems. $L4M J. Compul. 13 (1984), 1182-1196.
	15	F. van der Stappen, Motion Planning amidst Fat Obslacles, Ph.D. Dissertation, Utrecht {Tniversit, y, 1994.

CITED BY 8

	Matthew J. Katz , Franck Nielsen, On piercing sets of objects, Proceedings of the twelfth annual symposium on Computational geometry, p.113-121, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Doron Nussbaum, Rectilinear p-piercing problems, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.316-323, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Gill Barequet , Michael T. Goodrich , D. Z. Chen , O. Daescu , J. Snoeyink, Efficiently approximating polygonal paths in three and higher dimensions, Proceedings of the fourteenth annual symposium on Computational geometry, p.317-326, June 07-10, 1998, Minneapolis, Minnesota, United States
	Micha Sharir , Emo Welzl, Rectilinear and polygonal p-piercing and p-center problems, Proceedings of the twelfth annual symposium on Computational geometry, p.122-132, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	David Eppstein, Faster construction of planar two-centers, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.131-138, January 05-07, 1997, New Orleans, Louisiana, United States
	Maharaj Mukherjee , Kanad Chakraborty, A polynomial-time optimization algorithm for a rectilinear partitioning problem with applications in VLSI design automation, Information Processing Letters, v.83 n.1, p.41-48, 16 July 2002
	Po-Hsueh Huang , Yin Te Tsai , Chuan Yi Tang, A fast algorithm for the alpha-connected two-center decision problem, Information Processing Letters, v.85 n.4, p.205-210, 28 February 2003
	Mark A. Lanthier , Doron Nussbaum , Tsuo-Jung Wang, Calculating the meeting point of scattered robots on weighted terrain surfaces, Proceedings of the 2005 Australasian symposium on Theory of computing, p.107-118, January 01, 2005, Newcastle, Australia