Shooting permanent rays among disjoint polygons in the plane

ABSTRACT

We present a data structure for ray shooting-and-insertion in the free space among disjoint polygonal obstacles with a total of $n$ vertices in the plane, where each ray starts at the boundary of some obstacle. The portion of each query ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. Our data structure uses O(n log n) space and preprocessing time, and it supports m successive ray shooting-and-insertion queries in O(n log² n + m log m) total time. We present two applications for our data structure: (1) Our data structure supports efficient implementation of auto-partitions in the plane i.e. binary space partitions where each partition is done along the supporting line of an input segment. If n input line segments are fragmented into m pieces by an auto-partition, then it can now be implemented in O(n log²n+m log m) time. This improves the expected runtime of Patersen and Yao's classical randomized auto-partition algorithm for n disjoint line segments to O(n log² n). (2) If we are given disjoint polygonal obstacles with a total of n vertices in the plane, a permutation of the reflex vertices, and a half-line at each reflex vertex that partitions the reflex angle into two convex angles, then the folklore convex partitioning algorithm draws a ray emanating from each reflex vertex in the prescribed order in the given direction until it hits another obstacle, a previous ray, or infinity. The previously best implementation (with a semi-dynamic ray shooting data structure) requires O(n^3/2-ε/2) time using O(n^1+ε) space. Our data structure improves the runtime to O(n log² n).

REFERENCES

• 1: P. Agarwal and J. Erickson, Geometric range searching and its relatives, in: Adv. in Discrete and Comput. Geometry vol. 223 of Contemp. Maths, AMS, Providence, RI, 1999, pp. 1--56.
• 2: P. K. Agarwal, Range searching, in: Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, Eds., 2 ed. CRC Press LLC, Boca Raton, FL, 2004, ch. 36, pp. 809--838.
• 3: P. K. Agarwal, J. Basch, L. J. Guibas, J. E. Hershberger, and L. Zhang, Deformable free space tilings for kinetic collision detection, Int. J. Robotics Research 21 (3) (2002), 179--197.
• 4: 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]
• 5: Oswin Aichholzer , Sergey Bereg , Adrian Dumitrescu , Alfredo García , Clemens Huemer , Ferran Hurtado , Mikio Kano , Alberto Márquez , David Rappaport , Shakhar Smorodinsky , Diane Souvaine , Jorge Urrutia , David R. Wood, Compatible geometric matchings, Computational Geometry: Theory and Applications, v.42 n.6-7, p.617-626, August, 2009 [doi>10.1016/j.comgeo.2008.12.005]
• 6: M. Al-Jubeh, M. Hoffmann, M. Ishaque, D. L. Souvaine, and C. D. Tóth, Convex partitions with 2-edge connected dual graphs, in: Abstracts of the 18th Fall Workshop on Comput. Geom., 2008, pp. 62--63.
• 7: Julien Basch , Jeff Erickson , Leonidas J. Guibas , John Hershberger , Li Zhang, Kinetic collision detection between two simple polygons, Computational Geometry: Theory and Applications, v.27 n.3, p.211-235, March 2004 [doi>10.1016/j.comgeo.2003.11.001]
• 8: B. Chazelle, On the convex layers of a planar set, IEEE Trans. Inform. Theory IT-31 (4) (1985), 509--517.
• 9: B. Chazelle, H. Edelsbrunner, M. Grigni, L. J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink, Ray shooting in polygons using geodesic triangulations, Algorithmica 12 (1994), 54--68.
• 10: B. Chazelle, M. Sharir, and E. Welzl, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Algorithmica 8 (1992), 407--429.
• 11: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 12: M. de Berg, personal communication, March, 2009.
• 13: A. Ganguli, J. Cortes, and F. Bullo, Multirobot rendezvous with visibility sensors in nonconvex environments, IEEE Transactions on Robotics 25 (2) (2009), to appear.
• 14: Subir Ghosh, Visibility Algorithms in the Plane, Cambridge University Press, New York, NY, 2007
• 15: Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations, Journal of Algorithms, v.23 n.1, p.51-73, April 1997 [doi>10.1006/jagm.1995.0797]
• 16: L. J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Algorithmica 2 (1987), 209--233.
• 17: John Hershberger , Subhash Suri, Applications of a semi-dynamic convex hull algorithm, BIT, v.32 n.2, p.249-267, 1992 [doi>10.1007/BF01994880]
• 18: John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Journal of Algorithms, v.18 n.3, p.403-431, May 1995
• 19: Michael Hoffmann , Csaba D. Tóth, Segment endpoint visibility graphs are Hamiltonian, Computational Geometry: Theory and Applications, v.26 n.1, p.47-68, August 2003
• 20: Mashhood Ishaque , Csaba D. Tóth, Relative Convex Hulls in Semi-dynamic Subdivisions, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_65]
• 21: David Kirkpatrick , Bettina Speckmann, Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons, Proceedings of the eighteenth annual symposium on Computational geometry, p.179-188, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513423]
• 22: J. Matousek, Spanning trees with low crossing number, ITA 25 (1991), 103--124.
• 23: J. S. B. Mitchell, Geometric shortest paths and network optimization, in: Handbook of Computational Geometry, Elsevier, Amsterdam, 2000.
• 24: M. H. Overmars and J. van Leeuwen, Maintenance of configurations in the plane, J. Comput. Syst. Sci. 23 (1981), 166--204.
• 25: Michael S. Paterson , F. Frances Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete & Computational Geometry, v.5 n.5, p.485-503, 1990 [doi>10.1007/BF02187806]
• 26: M. Pellegrini, Ray shooting and lines in space, 2nd ed., CRC Press, Boca Raton, 2004, ch. 37, pp. 239--256.
• 27: J. Sklansky, R. L. Chazin, and B. J. Hansen, Minimum perimeter polygons of digitized silhouettes, IEEE Trans. Comput. C-21 (1972), 260--268.
• 28: B. Speckmann, Kinetic Data Structures for Collision Detection, PhD thesis, University of British Columbia, Vancouver, 2001.
• 29: Csaba D. Tóth, Binary plane partitions for disjoint line segments, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark [doi>10.1145/1542362.1542375]
• 30: Csaba D. Tóth, Binary Space Partitions for Line Segments with a Limited Number of Directions, SIAM Journal on Computing, v.32 n.2, p.307-325, 2003 [doi>10.1137/S0097539702403785]
• 31: G. T. Toussaint, Shortest path solves translation separability of polygons, Report SOCS-85.27, School Comput. Sci., McGill Univ., Montreal, QC, 1985.
• 32: G. T. Toussaint, An optimal algorithm for computing the relative convex hull of a set of points in a polygon, in: Signal Processing III: Theories and Applications. 1986, pp. 853--856.
• 33: Emo Welzl, On Spanning Trees with Low Crossing Numbers, Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, p.233-249, January 1992

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Design

Keywords:
binary space partition, convex partition, dynamic data structure, ray shooting, segment insertion