Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension

Full text

Pdf (805 KB)

Source

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

Waterloo, Ontario, Canada

Pages: 331 - 340

Year of Publication: 1987

ISBN:0-89791-231-4

Authors

N. Alon	Department of Mathematics, Tel Aviv University, Ramat Aviv, TEL Aviv 69978, Israel
D. Haussler	Computer Science Department, University of California at Santa Cruz, Santa Cruz, CA, USA
E. Welzl	Institutes for Information Processing, Technical University of Graz, Schiesstattgaser 4a, A-8010 GRAZ, Austria

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

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

	Al	N Alon, Expanders, sorting in rounds and superconcentrators of limited depth, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.98-102, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22156]
	A2	N Alon, Eigenvalues, geometric expanders, sorting in rounds, amd Ramsey theory, Combinatorica, v.6 n.3, p.207-219, 1986 [doi>10.1007/BF02579382]
	F	Yredman, M. L., Lower bounds on the complexity of some optimal dstostructures, SIAW J. Cornput. 1C (l!Ml) l-10.
	H	Hall, M.Jr., Combinatorial Theory, Wiley and Sons, New York, London (1967).
	HW	Haussler, D. and Welzl, Is., Bpsilonriots and simplex range search, Discrete and Conput. Geor., to appear.
	L	Lovasz, L., Combinatorial Problems and Exercises, North-Holland, Amsterdam, New York, Oxford (1979).
	S	Sauer, N., On the density of families of sets, J. Combin. Theory Ser. A 13 (1972) 145-147.
	VC	Vapnik, V.N. and Chervonenkis', A.YA., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Rpp.1. 16 (1971) 164-280.
	W	Willard, D., Polygon retrieval, SIAM .I. Cornput. 11 (1982) 149-165.
	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 5

	K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	David P. Helmbold , Manfred K. Warmuth, Some weak learning results, Proceedings of the fifth annual workshop on Computational learning theory, p.399-412, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	E. Welzl, Partition trees for triangle counting and other range searching problems, Proceedings of the fourth annual symposium on Computational geometry, p.23-33, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994
	Benjamin I. P. Rubinstein , Peter L. Bartlett , J. Hyam Rubinstein, Shifting: One-inclusion mistake bounds and sample compression, Journal of Computer and System Sciences, v.75 n.1, p.37-59, January, 2009