Approximations and optimal geometric divide-and-conquer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximations and optimal geometric divide-and-conquer

Full text

Pdf (664 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 505 - 511

Year of Publication: 1991

ISBN:0-89791-397-3

Author

Jiří Matoušek

Charles Univ., Prague, Czechoslovakia

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 50, Citation Count: 24

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/103418.103470 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.

	Agarwal 90	Pankaj K. Agarwal, Partitioning arrangements of lines, part I: an efficient deterministic algorithm, Discrete & Computational Geometry, v.5 n.5, p.449-483, 1990 [doi>10.1007/BF02187805]
	Blumer et al. 89	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]
	Chazelle,Friedman 90	B. Chazelle and J. Friedman: A deterministic view of random sampling and its use in geometry. Combinatorica, 10, 1990.
	Chazelle,Welzl 89	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]
	Haussler,Welzl 87	D. Haussler and E. Welzl: e-nets and simplex range queries. Discrete 8J Computational Geometry, 2:127-151, 1987.
	Komlós 90	J. KomlSs, manuscript, 1990.
	Matousek 90a	Jiří Matoušek, Construction of &egr;-nets, Discrete & Computational Geometry, v.5 n.5, p.427-448, 1990 [doi>10.1007/BF02187804]
	Matousek 90b	Jiří Matoušek, Cutting hyperplane arrangements, Proceedings of the sixth annual symposium on Computational geometry, p.1-9, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98528]
	Pach,Wöginger 90	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]
	Raghavan 86	P. Raghavan: Probabilistic construction of deterministic algorithms: approximating packing integer programs. In Proc. 27. IEEE Symposium on Foundations of Computer Science, pages 10-18, 1986.
	Sauer 72	N. Sauer: On the density of families of sets. Journal of Combin. Theory Set. A, 13:145-147, 1972.
	Spencer 87	R. Spencer: Ten lectures on the probabilistic method. CBMS-NSF, SIAM, 1987.
	Vapnik,Chervonenkis 71	V. N. Vapnik and A. Ya. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16:264- 280, 1971.

CITED BY 24

	Pankaj K. Agarwal , Jiří Mataušek, Relative neighborhood graphs in three dimensions, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.58-65, September 1992, Orlando, Florida, United States
	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
	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 , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, Diameter, width, closest line pair, and parametric searching, Proceedings of the eighth annual symposium on Computational geometry, p.120-129, June 10-12, 1992, Berlin, Germany
	Jiří Matoušek , Otfried Schwarzkopf, A deterministic algorithm for the three-dimensional diameter problem, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.478-484, May 16-18, 1993, San Diego, California, United States
	Jiří Matoušek , Chi-Yuan Lo , William Steiger, Ham-sandwich cuts in R^d, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.539-545, May 04-06, 1992, Victoria, British Columbia, Canada
	David Eppstein , Gary L. Miller , Shang-Hua Teng, A deterministic linear time algorithm for geometric separators and its applications, Proceedings of the ninth annual symposium on Computational geometry, p.99-108, May 18-21, 1993, San Diego, California, United States
	Jiří Matoušek , Otfried Schwarzkopf, Linear optimization queries, Proceedings of the eighth annual symposium on Computational geometry, p.16-25, June 10-12, 1992, Berlin, Germany
	Pankaj K. Agarwal , Micha Sharir, Ray shooting amidst convex polytopes in three dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.260-270, January 25-27, 1993, Austin, Texas, United States
	Nancy M. Amato , Edgar A. Ramos, On computing Voronoi diagrams by divide-prune-and-conquer, Proceedings of the twelfth annual symposium on Computational geometry, p.166-175, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Timothy M. Y. Chan , Jack Snoeyink , Chee-Keng Yap, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.282-291, January 22-24, 1995, San Francisco, California, United States
	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
	Jiří Matoušek, Range searching with efficient hierarchical cuttings, Proceedings of the eighth annual symposium on Computational geometry, p.276-285, June 10-12, 1992, Berlin, Germany
	Michael T. Goodrich, Fixed-dimensional parallel linear programming via relative &egr;-approximations, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.132-141, January 28-30, 1996, Atlanta, Georgia, 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
	K. L. Clarkson , David Eppstein , Gary L. Miller , Carl Sturtivant , Shang-Hua Teng, Approximating center points with iterated radon points, Proceedings of the ninth annual symposium on Computational geometry, p.91-98, May 18-21, 1993, San Diego, California, United States
	Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications, Proceedings of the eleventh annual symposium on Computational geometry, p.39-50, June 05-07, 1995, Vancouver, British Columbia, Canada
	Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , Micha Sharir , Emo Welzl, Improved bounds on weak &egr;-nets for convex sets, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.495-504, May 16-18, 1993, San Diego, California, United States
	Shreesh Jadhav , Asish Mukhopadhyay, Computing a centerpoint of a finite planar set of points in linear time, Proceedings of the ninth annual symposium on Computational geometry, p.83-90, May 18-21, 1993, San Diego, California, United States
	L. Paul Chew , Klara Kedem , Micha Sharir , Boaz Tagansky , Emo Welzl, Voronoi diagrams of lines in 3-space under polyhedral convex distance functions, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.197-204, January 22-24, 1995, San Francisco, California, United States
	Michael T. Goodrich, Geometric partitioning made easier, even in parallel, Proceedings of the ninth annual symposium on Computational geometry, p.73-82, May 18-21, 1993, San Diego, California, United States
	Jiří Matoušek, Efficient partition trees, Proceedings of the seventh annual symposium on Computational geometry, p.1-9, June 10-12, 1991, North Conway, New Hampshire, United States
	Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994
	Gary L. Miller , Donald R. Sheehy, Approximate center points with proofs, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark