The discrete 2-center problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The discrete 2-center problem

Full text

Pdf (1.34 MB)

Source

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

Nice, France

Pages: 147 - 155

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Pankaj K. Agarwal	Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NC
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
Emo Welzl	Institut für Theoretische Informatik, ETH Zürich, CH-8092, Zürich, Switzerland

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): 27, Citation Count: 7

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/262839.262921 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	Pankaj K. Agarwal, On stabbing lines for convex polyhedra in 3D, Computational Geometry: Theory and Applications, v.4 n.4, p.177-189, Aug. 1994 [doi>10.1016/0925-7721(94)90016-7]
	2	P.K. Agarwal, B. Aronov, M. Sharir and S. Suri, Selecting distances in the plane, Algorithmica 9 (1993), 495-514.
	3	P.K. Agarwal and M. Sharir, Planar geometric location problems, Algorithmica 11 (1994), 185-195.
	4	Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
	5	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	6	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
	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	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]
	9	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]
	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	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]
	12	N. Megiddo and K. Supowit, On the complexity of some common geometric location problems, SIAM J. Uomput. 13 (1984), 1182-1196.
	13	M. Reichling, On the detection of a common intersection of k convex objects in the plane, Information Processing Letters, v.29 n.1, p.25-29, Sept. 15, 1988 [doi>10.1016/0020-0190(88)90127-5]
	14	M. Sharir, A near-linear algorithm for the planar twocenter problem, Discrete Comput. Geom. (in press).
	15	Arie Tamir, Improved complexity bounds for center location problems on networks by using dynamic data structures, SIAM Journal on Discrete Mathematics, v.1 n.3, p.377-396, Aug. 1988 [doi>10.1137/0401038]

CITED BY 7

	Sándor P. Fekete , Joseph S. B. Mitchell , Karin Weinbrecht, On the continuous Weber and k-median problems (extended abstract), Proceedings of the sixteenth annual symposium on Computational geometry, p.70-79, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	Timothy M. Chan, Geometric applications of a randomized optimization technique, Proceedings of the fourteenth annual symposium on Computational geometry, p.269-278, June 07-10, 1998, Minneapolis, Minnesota, United States
	Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Journal of Algorithms, v.46 n.2, p.115-139, February 2003
	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
	Sergey Bereg , Michael Segal, Dynamic algorithms for approximating interdistances, Nordic Journal of Computing, v.11 n.4, p.344-355, December 2004
	Sasanka Roy , Debabrata Bardhan , Sandip Das, Base station placement on boundary of a convex polygon, Journal of Parallel and Distributed Computing, v.68 n.2, p.265-273, February, 2008