Lower bounds for off-line range searching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for off-line range searching

Full text

Pdf (714 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 733 - 740

Year of Publication: 1995

ISBN:0-89791-718-9

Author

Bernard Chazelle

Department of Computer Science, Princeton University, Princeton, NJ

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): 20, Citation Count: 3

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/225058.225291 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., Spencer, J. The ,Probabilistic Method, John Wiley & Sons, New York, 1992.
	2	Beck, J., Chen, W.W. L. Irregularities of distri-bution, Cambridge Tracts in Mathematics, 89, Cambridge univ. Press, Cambridge, 1987.
	3	Chazelle, B. Lower bounds on the complexity of polyto~ range searching, J. Amer. Math. Sot., 2 (1989), 637-666.
	4	Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990 [doi>10.1145/79147.79149]
	5	Chazelle, B. A spectral approach to lower bounds, Proc. 35th Ann. IEEE Symp. Foundat. ~Ci. (1994), 674-682.
	6	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 [doi>10.1145/195058.195110]
	7	Bernard Chazelle , Burton Rosenberg, Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.439-449, July 13-17, 1992
	8	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	9	Jeff Erickson, New lower bounds for Hopcroft's problem, Proceedings of the eleventh annual symposium on Computational geometry, p.127-137, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220293]
	10	Michael L. Fredman, A Lower Bound on the Complexity of Orthogonal Range Queries, Journal of the ACM (JACM), v.28 n.4, p.696-705, Oct. 1981 [doi>10.1145/322276.322281]
	11	Fredman, M.L. Lower bounds on the complexity of some optimal data structures, SIAM J. Com-put., 10 (1981), 1-10.
	12	Lancaster, P., Tismenetsky, M. The Theory of Matrices, 2nd cd., Academic Press, 1985.
	13	Matou~ek, J. Geometric range searching, Tech. Report B-93-o9, Free Univ. Berlin, 1993.
	14	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	15	Jacques Morgenstern, Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform, Journal of the ACM (JACM), v.20 n.2, p.305-306, April 1973 [doi>10.1145/321752.321761]
	16	Mulmuley, K. Computational Geometry: An Introduction Through Randomized Algorithms, Prentice-Hall, 1994.
	17	Roth, K.F. On irregularities of distribution, Mathematika, 1 (1954), 73-79.
	18	Yao, A.C. On the complexity of maintaining partial sums, SIAM J. Comput., 14 (1985), 277- 288.
	19	F. Frances Yao, Computational geometry, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

CITED BY 3

	Joseph M. Hellerstein , Elias Koutsoupias , Daniel P. Miranker , Christos H. Papadimitriou , Vasilis Samoladas, On a model of indexability and its bounds for range queries, Journal of the ACM (JACM), v.49 n.1, p.35-55, January 2002
	Jeff Erickson, New lower bounds for Hopcroft's problem, Proceedings of the eleventh annual symposium on Computational geometry, p.127-137, June 05-07, 1995, Vancouver, British Columbia, Canada
	Mihai Patrascu, Lower bounds for 2-dimensional range counting, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA