On piercing sets of objects

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On piercing sets of objects

Full text

Pdf (859 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: 113 - 121

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Matthew J. Katz	Department of Computer Science, Utrecht University
Franck Nielsen	INRIA, BP93, 06902 Sophia-Antipolis cedex (France)

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): 7, Downloads (12 Months): 15, Citation Count: 4

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.237253 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.

	Ame94	N. Amenta. Helly-type theorems and generalized linear programming. Discrete Cornput. Geom., 12:241-261, 1994.
	BGLR93	M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
	Chv79	V. Chvatal. A greedy heuristic for the setcovering problem. Math. Oper. Res., 4:233- 235, 1979.
	CM93	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
	DG82	L. Danzer and B. Griinbaum. Intersection properties of boxes in Rd. Combinatorica, 2(3):237-246, 1982.
	DGK63	L. Danzer, B. Griinbaum, and V. Klee. Helly's theorem and its relatives. In Proc. Syrup. Pure Math., pages 101-180, 1963.
	FPT81	R.J. Fowler, M. S. Paterson, and S. L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Inform. Process. Left., 12(3):133-137, 1981.
	GW93	P.M. Gruber and J. M. Wills, editors. Handbook of Convex Geometry, volume A. North-Holland, Amsterdam, the Netherlands, 1993.
	HD60	H. Hadwiger and H. Debrunner. Kombinatorische Geometric in der Ebene. Monographies de l'Enseignement Math~matique, N2, Geneva, 1960.
	Hoc82	D.S. Hochbaum. Approximation algorithms of the set covering and vertex cover problems. SIAM J. Computing, 11(3):555-556, 1982.
	Kar72	R. Karp. Reducibility among combinatorial problems, complexity of computer computations. E. Miller and J.W. Thatcher, New York, 1972.
	KN96	M. Katchalski and D. Nashtir. On a conjecture of Danzer and Griinbaum. In Proc. AMS, to appear.
	KNi96	M.J. Katz and F. Nielsen. On piercing sets of objects. INRIA Technical Report, to appear.
	Meg83	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]
	MSW92	Jiří Matoušek , Micha Sharir , Emo Welzl, A subexponential bound for linear programming, Proceedings of the eighth annual symposium on Computational geometry, p.1-8, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142678]
	Sha96	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]
	SW96	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 [doi>10.1145/237218.237255]

CITED BY 4

	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	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
	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
	Frank Nielsen, On point covers of c-oriented polygons, Theoretical Computer Science, v.263 n.1-2, p.17-29, July 28 2001