How to net a lot with little: small &egr;-nets for disks and halfspaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

How to net a lot with little: small &egr;-nets for disks and halfspaces

Full text

Pdf (653 KB)

Source

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

Berkley, California, United States

Pages: 16 - 22

Year of Publication: 1990

ISBN:0-89791-362-0

Authors

Jiří Matoušek	Department of Computer Science, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czechoslovakia
Raimund Seidel	Computer Science Division, University of California, Berkeley, Berkeley, CA
E. Welzl	Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, D-1000 Berlin 33, West Germany

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): 5, Downloads (12 Months): 24, Citation Count: 13

Additional Information:

abstract 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/98524.98530 What is a DOI?

ABSTRACT

It is known that in general range spaces of VC-dimension d > 1 require &egr;-nets to be of size at least &OHgr;(d/&egr; log 1/&egr;). We investigate the question whether this general lower bound is valid for the special range spaces that typically arise in computational geometry. We show that disks and pseudo-disks in the plane as well as halfspaces in R3 allow &egr;-nets of size only &Ogr;(1/&egr;), which is best possible up to a multiplicative constant. The analogous questions for higher-dimensional spaces remain open.

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.

	A	P. K. Agarwal, A deterministic algorithm for partitioning arrangements of lines and its application, Proceedings of the fifth annual symposium on Computational geometry, p.11-22, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73835]
	B*	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
	CF	B. Chazelle and J. Friedman, A Deterministic View of Random Sampling and its Use in Geometry, Proc. ~Yth IEEE FOCS (1988) 539-549.
	CW	B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
	C	K.L. Clarkson, New Applications of Random Sampiing in Computational Geometry, Discrete Computational Geometry 2 (1987) 195-22~.
	C1	K.L. Clarkson, Private Communication.
	ES	Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
	EW	H. Edelsbrunner and E. Welzl, On the Number of Line Separations of a Finite Set in the Plane, J. Combinatorial Theory Series A 38 (1985) 15-29.
	HW	D. Haussler and E. Welzl, ~-Nets and Simplex Range Queries, Discrete ~ Computational Geometry 2 (1987) ~37-~56.
	M	J. Matoušek, Construction of epsilon nets, Proceedings of the fifth annual symposium on Computational geometry, p.1-10, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73834]
	PW	János Pach , Gerhard Woeginger, Some new bounds for Epsilon-nets, Proceedings of the sixth annual symposium on Computational geometry, p.10-15, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98529]
	W	G. Wegner, 0ber eine kombinatoriseh-geometrische Frage yon Hadwiger und Debrunner, Israel J. of Math 3 (1965) 187-198.
	YY	A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]

CITED BY 13

	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
	János Pach , Gerhard Woeginger, Some new bounds for Epsilon-nets, Proceedings of the sixth annual symposium on Computational geometry, p.10-15, June 07-09, 1990, Berkley, California, United States
	Kenneth L. Clarkson , Kasturi Varadarajan, Improved approximation algorithms for geometric set cover, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Magnús M. Halldórsson , Takeshi Tokuyama, Minimizing interference of a wireless ad-hoc network in a plane, Theoretical Computer Science, v.402 n.1, p.29-42, July, 2008
	Stefan Funke , Alex Kesselman , Fabian Kuhn , Zvi Lotker , Michael Segal, Improved approximation algorithms for connected sensor cover, Wireless Networks, v.13 n.2, p.153-164, April 2007
	Ilias Diakonikolas , Mihalis Yannakakis, Succinct approximate convex pareto curves, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.74-83, January 20-22, 2008, San Francisco, California
	Kenneth L. Clarkson , C. Seshadhri, Self-improving algorithms for delaunay triangulations, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Sandeep Gupta , Jinfeng Ni , Chinya V. Ravishankar, Efficient data dissemination using locale covers, Pervasive and Mobile Computing, v.4 n.2, p.254-275, April, 2008
	Evangelia Pyrga , Saurabh Ray, New existence proofs ε-nets, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Pankaj K. Agarwal , Esther Ezra , Micha Shair, Near-linear approximation algorithms for geometric hitting sets, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Nabil Hassan Mustafa , Saurabh Ray, PTAS for geometric hitting set problems via local search, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Boris Aronov , Esther Ezra , Micha Shair, Small-size ε-nets for axis-parallel rectangles and boxes, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Kasturi Varadarajan, Epsilon nets and union complexity, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark