A trace bound for the hereditary discrepancy

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A trace bound for the hereditary discrepancy

Full text

Pdf (521 KB)

Source

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

Clear Water Bay, Kowloon, Hong Kong

Pages: 64 - 69

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

Bernard Chazelle	Department of Computer Science, Princeton University and NEC Research Institute
Alexey Lvov	Program in Applied and Computational Mathematics, Princeton University

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): 17, Citation Count: 0

Additional Information:

references 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/336154.336179 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	Beck, J., Chen, W.W.L. Irregularities of Distribution, Cambridge Tracts in Mathematics, 89, Cambridge University Press, Cambridge, 1987.
	2	Chazelle, B. Lower bounds .for off-line range searching, Disc. Comput. Geom., 17 (1997), 53-65.
	3	Bernard Chazelle, A Spectral Approach to Lower Bounds with Applications to Geometric Searching, SIAM Journal on Computing, v.27 n.2, p.545-556, April 1998 [doi>10.1137/S0097539794275665]
	4	Chazelle, B. Discrepancy bounds for geometric set systems with Square Incidence Matrices, in "Advances in Discrete and Computational Geometry," eds. B. Chazelle, J.E. Goodman and R. Pollack, Contemporary Mathematics, 223, AMS (1999), 103-107.
	5	The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
	6	Drmota, M., Tichy, R.F., Sequences, Discrepancies and Applications, Lecture Notes in Mathematics, Vol. 1651, Springer, March 1997.
	7	Huxley, M., On the difference between consecutive primes, Invent. Math. 15 (1972), 164-170.
	8	Kalbfleisch, J.G., Probability and Statistical Inference, Vol. 1, Springer-Verlag (1995), New York Inc.
	9	L Lovasz , J Spencer , K Vesztergombi, Discrepancy of set-systems and matrices, European Journal of Combinatorics, v.7 n.2, p.151-160, April 1986
	10	Lov~z, L., Vesztergombi, K. Extremal problems for discrepancy, In "Irregularities of partitions", G. Hal~z, V.T. S6s, eds. (1989), 107-113.
	11	Matou~ek, J. Geometric Discrepancy: An Illustrated Guide, Algorithms and Combinatorics, 18, Springer, 1999.
	12	Montgomery, H.L. Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, CBMS Regional Conference Series in Mathematics, No. 84), Amer. Math. Soc., Providence (1994).
	13	Pach, J., Agarwal, P.K. Combinatorial Geometry, John Wiley & Sons, 1995.
	14	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
	15	Szerem~di, E., Trotter, W. Extremal problems in discrete geometry, Combinatorica, 3 (1983), 381-392.