Good splitters for counting points in triangles

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Good splitters for counting points in triangles

Full text

Pdf (654 KB)

Source

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

Saarbruchen, West Germany

Pages: 124 - 130

Year of Publication: 1989

ISBN:0-89791-318-3

Authors

J. Matoušek	Department of Computer Science, Charles University, Malostranské nám. 25, 11600 Praha 1, Czechoslovakia
E. Welzl	Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, D-1000 Berlin 33

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): 2, Downloads (12 Months): 15, Citation Count: 1

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

ABSTRACT

A set A of n points in the plane has to be stored in such a way that for any query triangle t the number of points of A inside t can be computed efficiently. For this problem a solution is presented with &Ogr;(√n log n) query time, &Ogr; (n log n) space and &Ogr;(n3/2 log n) preprocessing time. The constants in the asymptotic bounds are small, and the method is easy to implement.

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.

	Br	Kevin Quentin Brown, Geometric transforms for fast geometric algorithms, 1979
	CGL	B.Chazelle, L.J.Guibas & D.T.Lee, The power of geometric duality, in "Proc. 25th IEEE Symp. on Foundations of Computer Science" (1983) 83-91.
	CW	B.Chazelle & E.Welzl, Range searching and VC-dimension: a characterization of efficiency, Discrete Comput. Geom. (1989), to appear.
	CSSS	R.Cole, J.Salowe, W.L.Steiger & E.Szeme&di, Optimal slope selection, manuscript.
	E	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	EGHSSSW	H. Edelsbrunner , L. J. Guibas , J. Hershberger , R. Seidel , M. Sharir, Implicitly representing arrangements of lines or segments, Proceedings of the fourth annual symposium on Computational geometry, p.56-69, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73400]
	EKM	H.Edelsbrunner, D.G. Kirkpatrick & H.A. Maurer, Polygon intersection searching, Inform. Process. Lett. 14 (1982) 74-79.
	EW	H Edelsbrunner , E Welzl, Halfplanar range search in linear space and O(n0.695) query time, Information Processing Letters, v.23 n.6, p.289-293, Dec. 3, 1986
	ES	P.Erd~s & G.Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935) 463-470.
	HW	D.Haussler & E.Welzl, Epsilon-nets and simplex range queries, Disc&e Comput. Geom. 2 (1987) 237-256.
	M1	Juřrí Matoušsek, Line arrangements and range search, Information Processing Letters, v.27 n.6, p.275-280, May 13, 1988 [doi>10.1016/0020-0190(88)90213-X]
	M2	J.MatouSek, Spanning trees with low stabbing number, manuscript.
	Wi	D.E.Willard, Polygon retrieval, SIAM J. Comput. 11 (1982) 149-165.