Abstract
In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m 2/3 n 2/3 · log2/3 n · logω/3 (m/√n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where ω is a constant <3.33; (ii) anO(m 2/3 n 2/3 · log5/3 n · logω/3 (m/√n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n 4/3 log(ω+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n 4/3 log(ω + 2)/3 n) algorithm to count “red-blue” intersections between two sets of segments, and (v) anO(n 3/2 logω/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(n√m logω+1/2 n), into a data structure of sizeO(m) forn logn≤m≤n 2, so that the number of points ofS lying inside a query triangle can be computed inO((n/√m) log3/2 n) time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number,Proceedings of the 5th Annual Symposium on Computational Geometry, 1989, pp. 315–325.
P. K. Agarwal, Intersection and decomposition algorithms for arrangements of curves in the plane, Ph.D. Thesis, Dept. Computer Science, New York University, New York, August 1989.
P. K. Agarwal, Partitioning arrangements of lines: I. An efficient deterministic algorithm,Discrete and Computational Geometry, this issue (1990), 449–483.
P. K. Agarwal and M. Sharir, Red-blue intersection detection algorithms with applications to motion planning and collision detection,SIAM Journal of Computing 19 (1990), 297–322.
B. Aronov, H. Edelsbrunner, L. Guibas, and M. Sharir, Improved bounds on the complexity of many faces in arrangements of segments, Technical Report 459, Dept. Computer Science, New York University, July 1989.
J. Bentley and T. Ottmann, Algorithms for reporting and counting geometric intersections,IEEE Transactions on Computers 28 (1979), 643–647.
K. Brown, Algorithms for reporting and counting geometric intersections,IEEE Transactions on Computers 30 (1981), 147–148.
R. Canham, A theorem on arrangements of lines in the plane,Israel Journal of Mathematics 7 (1969), 393–397.
B. Chazelle, Reporting and counting segment intersections,Journal of Computer and Systems Sciences 32 (1986), 156–182.
B. Chazelle, Lower bounds on the complexity of polytope range searching,Journal of the American Mathematical Society 2 (1989), 637–666.
B. Chazelle, Private communication.
B. Chazelle and H. Edelsbrunner, An optimal algorithm for intersecting line segments in the plane,Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 590–600. (Also to appear inJournal of the Association for Computing Machinery.)
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Algorithms for bichromatic line segment problems and polyhedral terrains, Manuscript, 1989.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Lines in space: combinatorics, algorithms and applications,Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989.
B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry,Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 539–549.
B. Chazelle and L. Guibas. Fractional cascading: II. Applications,Algorithmica 1 (1986), 163–191.
B. Chazelle, L. Guibas, and D. T. Lee, The power of geometric duality,BIT 25 (1985), 76–90.
B. Chazelle and E. Welzl, Quasi-optimal range searching in spaces with finite VC-dimension,Discrete and Computational Geometry 4 (1989), 467–490.
K. Clarkson, New applications of random sampling in computational geometry,Discrete and Computational Geometry 2 (1987), 195–222.
K. Clarkson, Applications of random sampling in computational geometry II,Proceedings of the 4th Annual Symposium on Computational Geometry, 1988, pp. 1–11.
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and surfaces,Discrete and Computational Geometry 5 (1990), 99–160.
R. Cole and M. Sharir, Visibility problems for polyhedral terrains,Journal of Symbolic Computation 7 (1989), 11–30.
R. Cole, M. Sharir, and C. K. Yap, onk-hulls and related problems,SIAM Journal on Computing 16 (1987), 61–77.
F. Dévai, Quadratic bounds for hidden line elimination,Proceedings of the 2nd Annual Symposium on Computational Geometry, 1986, pp. 269–275.
H. Edelsbrunner and L. Guibas, Topologically sweeping an arrangement,Journal of Computer and Systems Sciences 38 (1989), 165–194.
H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl, Implicitly representing arrangements of lines or segments,Discrete and Computational Geometry 4 (1989), 433–466.
H. Edelsbrunner, L. Guibas, and M. Sharir, The complexity and construction of many faces in arrangements of lines and segments,Discrete and Computational Geometry 5 (1990), 161–196.
H. Edelsbrunner, L. Guibas, and G. Stolfi, Optimal point location in monotone subdivisions,SIAM Journal on Computing 15 (1986), 317–340.
H. Edelsbrunner, J. O'Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications,SIAM Journal of Computing 15 (1986), 341–363.
H. Edelsbrunner and E. Welzl, Constructing belts in two-dimensional arrangements with applications,SIAM Journal on Computing 15 (1986), 271–284.
H. Edelsbrunner and E. Welzl, On the maximal number of edges of many faces in an arrangement,Journal of Combinatorial Theory, Series A 41 (1986), 159–166.
L. Guibas, M. Overmars, and M. Sharir, Ray shooting, implicit point location, and related queries in arrangements of segments, Technical Report 433, Dept. Computer Science, New York University, March 1989.
L. Guibas, M. Overmars, and M. Sharir, Counting and reporting intersections in arrangements of line segments, Technical Report 434, Dept. Computer Science, New York University, March 1989.
D. Haussler and E. Welzl, ɛ-nets and simplex range queries,Discrete and Computational Geometry 2 (1987), 127–151.
D. Kirkpatrick, Optimal search in planar subdivisions,SIAM Journal on Computing 12 (1983), 28–35.
H. Marison and J. Stolfi, Reporting and counting intersections between two sets of line segments, inTheoretical Foundations of Computer Graphics and CAD, ed. R. Earnshaw, NATO ASI Series, F40, Springer-Verlag, Berlin, 1988, pp. 307–325.
J. Matoušek, Constructing spanning trees with low crossing numbers, to appear inInformatique Théorique et Appliquée.
J. Matoušek, Construction of ɛ-nets,Discrete and Computational Geometry 5 (1990), 427–448.
J. Matoušek and E. Welzl, Good splitters for counting points in triangles,Proceedings of the 5th Annual Symposium on Computational Geometry, 1989, pp. 124–130. (Also to appear inJournal of Algorithms.)
M. McKenna, Worst case optimal hidden surface removal,ACM Transactions on Graphics 6 (1987), 9–31.
K. Mulmuley, A fast planar partition algorithm,Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 580–589.
F. Preparata and M. Shamos,Computational Geometry: An Introduction, Springer-Verlag, Heidelberg, 1985.
N. Sarnak and R. Tarjan, Planar point location using persistent search trees,Communications of the Association for Computing Machinery,29 (1986), 669–679.
E. Szemerédi and W. Trotter Jr., Extremal problems in discrete geometry,Combinatorica 3 (1983), 381–392.
E. Welzl, Partition trees for triangle counting and other range searching problems,Proceedings of the 4th Annual Symposium on Computational Geometry, 1988, pp. 23–33.
Author information
Authors and Affiliations
Additional information
Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.
Rights and permissions
About this article
Cite this article
Agarwal, P.K. Partitioning arrangements of lines II: Applications. Discrete Comput Geom 5, 533–573 (1990). https://doi.org/10.1007/BF02187809
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187809