Segment intersection searching problems in general settings

ABSTRACT

We consider segment intersection searching amidst (possibly intersecti ng) algebraic arcs in the plane. We show how to preprocess $n$ arcs in time $O(n^{2+\epsilon})$ into a data structure of size $O(n^{2+\epsilon})$, for any $\epsilon >0$, such that the $k$ arcs intersecting a query segment can be counted in time $O(\log n)$ or reported in time $O(\log n+k)$. This problem was extensively studied in restricted settings (e.g., amidst segments, circles or circular arcs), but no solution with comparable performance was previously presented for the general case of possibly intersecting algebraic arcs. Our data structure for the general case matches or improves (sometimes by an order of magnitude) the size of the best previously presented solutions for the special cases.As an immediate application of this result, we obtain an efficient data structure for the triangular windowing problem, which is a generalization of triangular range searching. As another application, the first substantially sub-quadratic algorithm for a red-blue intersection counting problem is derived. We also describe simple data structures for segment intersection searching among disjoint arcs, and ray shooting among algebraic arcs.

REFERENCES

• 1: P. K. Agarwal. Intersection and decomposition algorithms for planar arrangements. Cambridge University Press, New York, NY, 1991.
• 2: Pankaj K. Agarwal, Range searching, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 3: P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pages 1-56. American Mathematical Society, Providence, RI, 1999.
• 4: Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, SIAM Journal on Computing, v.22 n.4, p.794-806, Aug. 1993 [doi>10.1137/0222051]
• 5: Pankaj K. Agarwal , Marco Pellegrini , Micha Sharir, Counting circular arc intersections, SIAM Journal on Computing, v.22 n.4, p.778-793, Aug. 1993 [doi>10.1137/0222050]
• 6: Pankaj K. Agarwal , Micha Sharir, Applications of a new space-partitioning technique, Discrete & Computational Geometry, v.9 n.1, p.11-38, 1993 [doi>10.1007/BF02189304]
• 7: Pankaj K. Agarwal , Micha Sharir, Circle shooting in a simple polygon, Journal of Algorithms, v.14 n.1, p.69-87, Jan. 1993 [doi>10.1006/jagm.1993.1004]
• 8: Pankaj K. Agarwal , Marc van Kreveld , Mark Overmars, Intersection queries in curved objects, Journal of Algorithms, v.15 n.2, p.229-266, Sept. 1993 [doi>10.1006/jagm.1993.1040]
• 9: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, v.84 n.1, p.77-105, July 22, 1991 [doi>10.1016/0304-3975(91)90261-Y]
• 10: B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems. Algorithmica, 8:407-429, 1992.
• 11: Siu-Wing Cheng , Hazel Everett , Otfried Cheong , René van Oostrum, Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons, Proceedings of the fifteenth annual symposium on Computational geometry, p.227-236, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304976]
• 12: Mark de Berg, Ray Shooting, Depth Orders and Hidden Surface Removal, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 13: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 14: Prosenjit Gupta , Ravi Janardan , Michiel Smid, Further results on generalized intersection searching problems: counting, reporting, and dynamization, Journal of Algorithms, v.19 n.2, p.282-317, Sept. 1995 [doi>10.1006/jagm.1995.1038]
• 15: Sariel Har-Peled , Micha Sharir, Online point location in planar arrangements and its applications, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.57-66, January 07-09, 2001, Washington, D.C., United States
• 16: D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete Comput. Geom., 2:127-151, 1987.
• 17: Marco Pellegrini, Ray shooting and lines in space, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 18: Michel Pocchiola , Gert Vegter, Pseudo-triangulations: theory and applications, Proceedings of the twelfth annual symposium on Computational geometry, p.291-300, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237398]
• 19: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 20: Jack Snoeyink, Point location, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Theory