Improved bounds on weak &egr;-nets for convex sets

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved bounds on weak &egr;-nets for convex sets

Full text

Pdf (1.07 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 495 - 504

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Bernard Chazelle
Herbert Edelsbrunner
Michelangelo Grigni
Leonidas Guibas
Micha Sharir
Emo Welzl

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 11, Citation Count: 5

Additional Information:

references cited by 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/167088.167222 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	Alon, N., B~r#ny, I., Fiiredi, Z., Kleitman, D. Point selections and weak e-nets for convex hulls, Combin. Prob. and Computing 1, submitted.
	2	Alon, N., Kleitman, D. Piercing convex sets and the Hadwiger Debrunner (p, q)-problem, Adv. Math. (to appear).
	3	Boris Aronov , Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Rephael Wenger, Points and triangles in the plane and halving planes in space, Discrete & Computational Geometry, v.6 n.5, p.435-442, 1991
	4	Berger, M. Geometry 11, Springer-Verlag, 1987.
	5	Capoyleas, V. An almost linear upper bound for weak ~-nets of points in convex position, manuscript, 1992.
	6	Chazelle, B. Cutting hvperplanes for divide-andconquer, Disc. Comput. Geom. (1991), in press. Also, CS-TR-335-91, Princeton University, 1991. Prelim. version in Proc. 32nd FOCS, 1991.
	7	Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , John E. Hershberger , Raimund Seidel , Micha Sharir, Slimming down by adding; selecting heavily covered points, Proceedings of the sixth annual symposium on Computational geometry, p.116-127, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98551]
	8	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
	9	Coxeter, H.M.S. Non-Euclidean Geometry, Univ. Toronto Press, Toronto, 1942.
	10	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	11	Epstein, D.B.A. Analytical and Geometric Aspects of Hyperbolic Space, London Math. Society Lecture Notes Series 111, 1984.
	12	Fenchel, W. Elementary Geometry in Hyperbolic Space, de Gruyter Studies in Mathematics 11, 1989.
	13	Haussler, D., Welzl, E. Epsilon nets and simplex range queries, Discrete Comput. Geom. 2 (1987), 127-151.
	14	Magnus, W. Noneuclidean tesselations and their groups, Academic Press, New York and London, 1974.
	15	Matou#ek, J. Private communication, 1992.
	16	Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
	17	Milnor, J. Hyperbolic geometry: the first 150 years, Bull. Amer. Math. Soc. 6 (1982), 9-24.
	18	Thurston, W.P. The Geometry and Topology of 3- manifolds, Princeton Univ. Math. Dept. 1979.

CITED BY 5

	Saurabh Ray , Nabil Mustafa, An optimal generalization of the centerpoint theorem, and its extensions, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Saurabh Ray , Nabil Mustafa, Weak ε-nets have basis of size o(1/ε log (1/ε)) in any dimension, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Nabil H. Mustafa , Saurabh Ray, Weak ε-nets have basis of size O (1/εlog(1/ε)) in any dimension, Computational Geometry: Theory and Applications, v.40 n.1, p.84-91, May, 2008
	Hervé Brönnimann , Michael T. Goodrich, Almost optimal set covers in finite VC-dimension: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.293-302, June 06-08, 1994, Stony Brook, New York, United States
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada