The 2-center problem with obstacles

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The 2-center problem with obstacles

Full text

Pdf (1.13 MB)

Source

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

Clear Water Bay, Kowloon, Hong Kong

Pages: 80 - 90

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

Dan Halperin	Department of Computer Science, Tel Aviv University, Tel-Aviv, 69978, Israel
Micha Sharir	School of Mathematical Sciences, Tel Aviv University, Tel-Aviv, 69978, Israel, and Courant Institute of Mathematical Sciences, New York, University, New York, NY
Ken Goldberg	Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA

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): 1, Downloads (12 Months): 19, Citation Count: 0

Additional Information:

references index terms collaborative colleagues peer to peer

Tools and Actions:	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/336154.336184 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	Timothy M. Chan, More planar two-center algorithms, Computational Geometry: Theory and Applications, v.13 n.3, p.189-198, Sept. 1999 [doi>10.1016/S0925-7721(99)00019-X ]
	2	Siu-Wing Cheng , Hazel Everett , Otfried Cheong , René van Oostrum, Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons, Proceedings of the fifteenth annual symposium on Computational geometry, p.227-236, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304976]
	3	Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
	4	Richard Cole , Jeffrey S. Salowe , W. L. Steiger , Endre Szemerédi, An optimal-time algorithm for slope selection, SIAM Journal on Computing, v.18 n.4, p.792-810, Aug. 1989 [doi>10.1137/0218055]
	5	John J. Craig, Geometric algorithms in AdeptRAPID, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, p.133-139, August 1998, Houston, Texas, United States
	6	David Eppstein, Dynamic three-dimensional linear programming, Proceedings of the 32nd annual symposium on Foundations of computer science, p.488-494, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185410]
	7	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
	8	D. Halperin and C. Linhart. The minimum enclosing disk with obstacles. Manuscript, 1999. Java applet: http://www, m a t h .tau .ac.il/,~ ha I perin / projects, html.
	9	P. Hansen, B. Jaumard, and H. Tuy. Global optimization in location. In Z. Drezner, editor, Facility Location, pages 43-68. Springer-Verlag, New York, 1995.
	10	Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
	11	Jiří Matoušek , Nathaly Miller , Micha Sharir , Shmuel Sifrony , János Pach , Emo Welzl, Fat triangles determine linearly many holes, Proceedings of the 32nd annual symposium on Foundations of computer science, p.49-58, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185347]
	12	N. Megiddo. Linear-time algorithms for linear programming in Rs and related problems. SIAM Y. Comput., 12:759-776, 1983.
	13	N. Megiddo and K. J. Supowit. On the complexity of some common geometric location problems. SIAM J. Comput., 13(1):182-196, 1984.
	14	M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. Y. Comput. Syst. Sci., 23:166-204, 1981.
	15	M. Sharir. A near-linear algorithm for the planar 2-center problem. Discrete Comput. Geom., 18:125-134, 1997.