Rectilinear and polygonal p-piercing and p-center problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Rectilinear and polygonal p-piercing and p-center problems

Full text

Pdf (1.40 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 122 - 132

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Micha Sharir	School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY
Emo Welzl	Institut für Informatik, Freie Universität Berlin and Department 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): 6, Downloads (12 Months): 48, Citation Count: 14

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.237255 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.K. Agarwal and M. Sharir, Algorithmic techniques for geometric optimization, in: Lecture Notes in Computer Science, Vol. 1000, Springer-Verlag, 1995, pp. 234-253.
	2	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Journal of Algorithms, v.17 n.3, p.292-318, Nov. 1994
	3	N. Amenta, Helly-type theorems and generalized linear programming, Discrete Comput. Geom. 12 (1994), 241-261.
	4	Nina Amenta, Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem, Proceedings of the tenth annual symposium on Computational geometry, p.340-347, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178064]
	5	Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
	6	L. Danzer and B. GrSnbaum, Intersection properties of boxes in litd, Combinatorica 2 (1982), 237-246.
	7	Z. Drezner, The p-center problem: Heuristics and optimal algorithms, J. Oper. Res. Soc. 35 (1984), 741-748.
	8	Z. Drezner, On the rectangular p-center problem, Naval Res. Logist. Quart. 34 (1987), 229-234.
	9	J. Eckhoff, Helly, Radon, and Carathdodory type theorems, in Handbook of Convex Geometry (P. M. Gruber, J. M. Wills, Eds.) A (1993), 389-448.
	10	J. Elzinga and D. W. Hearn, Geometrical solution for some minimax location problems, Transportation Sci. 6 (1972), 379- 394.
	11	R.L. Francis and J. A. White, Facility Layout and Location, Prontieo Hall, Englaw55d Cliffs, New Jersey' (19q'4).
	12	Greg N. Frederickson, Optimal algorithms for tree partitioning, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.168-177, January 28-30, 1991, San Francisco, California, United States
	13	G. Frederickson and D. Johnson, The complexity of selection and ranking in X + Y and matrices with sorted columns, J. Comput. Syst. $ci. 24 (1982), 197-208.
	14	G. Frederickson and D. Johnson, Finding the k-th shortest paths and p-centers by generating and searching good data structures, J. Algorithms 4 (1983), 61-80.
	15	G. Frederickson and D. Johnson, Generalized selection and ranking: sorted matrices, SIAM J. Comput. 13 (1984), 14-30.
	16	H. Gabow and R. Tarjan, A linear time algorithm for a speciaJ case of disjoint set union, J. Comput. Syst. Sciences 30 (1985), 209-221.
	17	Alex Glozman , Klara Kedem , Gregory Shpitalnik, On Some Geometric Selection and Optimization Problems via Sorted Matrices, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.26-37, August 16-18, 1995
	18	M. Golumbic, Algorithmic Graph Theory, Academic Press, New York, 1980.
	19	O. Kariv and S. L. Hakimi, An algorithmic approach to network location problems. I: The p-centers, SIAM J. Appl. Math. 37 (1979), 513-538.
	20	M. Katchalski and D. Nashtir, On a conjecture of Danzer and Gr/inbaum, Proc. AMS, to appear.
	21	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 [doi>10.1145/237218.237253]
	22	M. T. Ko , Y. T. Ching, Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l∞ -distance, Discrete Applied Mathematics, v.40 n.3, p.397-410, Dec. 14, 1992 [doi>10.1016/0166-218X(92)90009-Y]
	23	M. T. Ko , R. C. T. Lee, On weighted rectilinear 2-center and 3-center problems, Information Sciences: an International Journal, v.54 n.1-2, p.169-190, March 1991 [doi>10.1016/0020-0255(91)90050-5]
	24	M. T. Ko, R. C. T. Lee, and J. S. Chang, Rectilinear mcenter problem, Proc. National Computer Syrup., Taipei, Taiwan, R.O.C. (1987), 325-329.
	25	M. T. Ko, R. C. T. Lee, and J. S. Chang, On optimal approximation for the rectilinear m-center problem, Algorithmica 5 (1990), 341-352.
	26	J. Matouiek, M. Sharir, and E. Welzl, A subexponential bound for linear programming and related problems, Algorithmica, to appear.
	27	N. Megiddo, Linear time algorithms for linear time programming in Rs and related problems, SIAM J. Comput. 12 (1983), 759-776.
	28	N. Megiddo, The weighted Euclidean l-center problem, Math. Oper. Res. 8 (1983), 498-504.
	29	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]
	30	N. Megiddo and A. Tamir, New results on the complexity of p-center problems, SIAM J. Comput. 12 (1983), 751-758.
	31	N. Megiddo and K. Supowit, On the complexity of some common geometric location problems, SIAM J. Comput. 13 (1984), 182-196.
	32	M. Overmars and J. van Leeuwen, Maintenance of configurations in the plane, J. Comp. System Sciences 23 (1981), 166-204.
	33	Micha Sharir, A near-linear algorithm for the planar 2-center problem, Proceedings of the twelfth annual symposium on Computational geometry, p.106-112, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237251]
	34	Micha Sharir , Emo Welzl, A Combinatorial Bound for Linear Programming and Related Problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.569-579, February 13-15, 1992

CITED BY 14

	Hai Huang , Andréa W. Richa , Michael Segal, Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	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
	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
	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
	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
	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
	Michael Hoffmann, A simple linear algorithm for computing rectilinear 3-centers, Computational Geometry: Theory and Applications, v.31 n.3, p.150-165, June 2005
	Nir Halman, A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane, Information Processing Letters, v.86 n.3, p.121-128, 16 May 2003
	Hai Huang , Andréa W. Richa , Michael Segal, Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks, Mobile Networks and Applications, v.9 n.2, p.151-161, April 2004
	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
	Esther M. Arkin , Gill Barequet , Joseph S. B. Mitchell, Algorithms for two-box covering, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Sergio Cabello , Panos Giannopoulos , Christian Knauer , Günter Rote, Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.836-843, January 20-22, 2008, San Francisco, California
	Mark de Berg , Shripad Thite, Cache-oblivious selection in sorted X+Y matrices, Information Processing Letters, v.109 n.2, p.87-92, December, 2008