Ray shooting and other applications of spanning trees with low stabbing number

ABSTRACT

In this paper we consider the following problem: Given a set @@@@ of n (possibly intersecting) line segments in the plane, preprocess them so that, given a query ray &rgr; emanating from a point p, we can quickly compute the intersection point &PHgr;(@@@@, &rgr;) of &rgr; with a segment of @@@@ that lies nearest to p. We present an algorithm that preprocesses @@@@, in time &Ogr;(n3/2 log&ohgr; n), into a data structure of size &Ogr;(n&agr;(n) log4 n), so that for a query ray &rgr;, &PHgr;(@@@@, &rgr;) can be computed in &Ogr;(√nlog3 n), where &ohgr; is a constant < 4.3 and &agr;(n) is a functional inverse of Ackermann's function. If the given segments are non-intersecting, the storage goes down to &Ogr;(nlog3 n) and the query time is only &Ogr;(√n log2 n). The main tool that we use is spanning trees with low stabbing number, i.e. with the property that no line intersects more than &Ogr;(√n) edges of the tree. Using such trees we obtain faster algorithms for several other problems, including implicit point location, polygon containment and implicit hidden surface removal.

REFERENCES

• Ag: P. K. Agarwal, A deterministic algorithm for partitioning arrangements of lines and its application, Proceedings of the fifth annual symposium on Computational geometry, p.11-22, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73835]
• Aga: P. K. Agarwal, Partitioning arrangements of lines: I. An efficient deterministic algorithm, manuscript, 1989.
• Agb: P. K. Agarwal, Partitioning arrangements of lines: II. Applications, manuscript, 1989.
• Age: P. K. Agarwal, Ray-shooting and other applications of spanning trees with low stabbing number, manuscript, 1989.
• Cha: B. Chazelle, Polytope range searching and integral geometry, Proceedings 28 th Annual IEEE Symp osium on Foundations of Computer Science, 1987, pp. l-10.
• Chb: B. Chazelle, Tight bounds on the stabbing number of trees in Euclidean plane, Technical Report CS-TR-155-58, Dept. Computer Science, Princeton University, May 1988.
• Chc: B. Chazelle, Private communication, 1989.
• CGa: Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
• CGb: B. Chazelle and L. Guibas, Fractional Cascading: I. A data structuring technique, Algorithmica, 1 (1986), pp. 133-162.
• CGc: B. Chazelle and L. Guibas, Fractional Cascading: II. Applications, Algorithmica, 1 (1986), pp. 163-192.
• Cw: B. Chazelle and E. Welzl, Range searching and VC- dimension: A characterization of efficiency, manuscript, 1988.
• Cl: K. Clarkson, New applications of random sampling in computational geometry, Discreie and Compulational Geometry, 2 (1987), pp. 195-222.
• CEG*: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir and E. Welzl, Combinatorial complexity bounds for arrangements of curves and surfaces, Proceedings 2gth Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 568-579.
• Co: Richard Cole, Searching and sorting similar lists, Journal of Algorithms, v.7 n.2, p.202-220, June 1986 [doi>10.1016/0196-6774(86)90004-0]
• De: F Devai, Quadratic bounds for hidden line elimination, Proceedings of the second annual symposium on Computational geometry, p.269-275, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10544]
• DE: David P. Dobkin , Herbert Edelsbrunner, Space searching for intersecting objects, Journal of Algorithms, v.8 n.5, p.348-361, Sept. 1987 [doi>10.1016/0196-6774(87)90015-0]
• DSST: 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]
• EG: Herbert Edelsbrunner , Leonidas Guibas, Topologically sweeping an arrangement, Journal of Computer and System Sciences, v.38 n.1, p.165-194, February 1989 [doi>10.1016/0022-0000(89)90038-X]
• EGH*: 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]
• EGP*: Herbert Edelsbrunner , Leonidas J. Guibas , János Pach , Richard Pollack , Raimund Seidel , Micha Sharir, Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.214-229, July 11-15, 1988
• EGSh: H. Edelsbrunner , L. J. Guibas , M. Sharir, The complexity of many faces in arrangements of lines of segments, Proceedings of the fourth annual symposium on Computational geometry, p.44-55, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73399]
• EGS: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• EOS: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• 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
• GHLST: L. Guibas, J. Hershberger, D. Leven, M. Sharir and Ft. Tarjan, Linear time algorithms for shortest path and visibility problems, Algorithmica, 2 (1987) pp. 209-233.
• GOS: L. Guibas, M. OvemLars and M. Sharir, Intersecting line segments, ray shootings and other applications of geometric partitioning techniques, Technical Report RUU-CS-88- 26, Dept. Computer Science, University of Utrecht, August 1988.
• GSS: L. J. Guibas , M. Sharir , S. Sifrony, On the general motion planning problem with two degrees of freedom, Proceedings of the fourth annual symposium on Computational geometry, p.289-298, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73423]
• Gu: L. Guibas and F. Yao. On translating a set of rectangles, in Advances in Compuier Rerearch, Vol. 1 (F. P. Preparata, ed.), JAI Press, 1983, pp. 61-77.
• HW: D. Haussler and E. Welzl, c-nets and simplex range queries, Dircrete and Compulahonol Geomeby, 2 (1987), pp. 127- 151.
• Ki: D. Kirkpatrick, Optimal search in planar subdivisions, SIAM .I. Computing, 12 (1983), pp. 28-35.
• MK: Michael McKenna, Worst-case optimal hidden-surface removal, ACM Transactions on Graphics (TOG), v.6 n.1, p.19-28, Jan. 1987 [doi>10.1145/27625.27627]
• Maa: J. Matotiek, Construction of c-nets, Proceedings Sth Annual Symposium on Computational Geometry, 1989.
• Mab: J. MatouZek, Spanning trees with low crossing numbers, manuscript, 1989.
• PSS: R. Pollack , M. Sharir , S. Sifrony, Separating two simple polygons by a sequence of translations, Discrete & Computational Geometry, v.3 n.2, p.123-136, Jan, 1988 [doi>10.1007/BF02187902]
• SO: S Suri , J O'Rourke, Worst-case optimal algorithms for constructing visibility polygons with holes, Proceedings of the second annual symposium on Computational geometry, p.14-23, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10517]
• ST: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• We: E. Welzl, Partition trees for triangle counting and other range searching problems, Proceedings of the fourth annual symposium on Computational geometry, p.23-33, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73397]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms

General Terms:
Algorithms, Theory