Ray shooting and intersection searching amidst fat convex polyhedra in 3-space

ABSTRACT

We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in R³. The data structure uses O(n^2+ε) storage and preprocessing time, and queries can be answered in O(log² n) time. A trade-off between storage and query time is also possible: for any m with n < m < n², we can construct a structure that uses O(m^1+ε) storage and preprocessing time such that queries take O((n/√m)log² n) time.We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in R³. For any m with n < m < n³, we can construct a structure that uses O(m^1+ε) storage and preprocessing time such that all polyhedra intersecting a query simplex can be reported in O((n/m^1/3)log n+k) time, where k is the number of answers.

REFERENCES

• 1: Pankaj K. Agarwal, Range searching, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 2: P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Contemporary Mathematics, volume 223, pages 1--56. American Mathematical Society, 1998.
• 3: 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]
• 4: P. K. Agarwal and J. Matoušek. On range-searching with semi-algebraic sets. Discrete and Computational Geometry, 11:393--418, 1993.
• 5: B. Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, and J. Stolfi. Lines in space: Combinatorics and algorithms. Algorithmica, 15(5):428--447, 1996.
• 6: Mark de Berg, Ray Shooting, Depth Orders and Hidden Surface Removal, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 7: M. de Berg. Linear size binary space partitions for uncluttered scenes. Algorithmica, 28:353--366, 2000.
• 8: Mark de Berg, Vertical ray shooting for fat objects, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064137]
• 9: Mark de Berg , Chris Gray, Vertical ray shooting and computing depth orders for fat objects, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.494-503, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109612]
• 10: M. de Berg and M. Streppel. Approximate range searching using binary space partitions. In Proc. 24th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 110--121, 2004.
• 11: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 12: D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection. Theoretical Computer Science, 27(3):241--253, 1983.
• 13: J. Erickson. New lower bounds for Hopcroft's problem. Discrete and Computational Geometry, 16:389--418, 1996.
• 14: Matthew J. Kaltz, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, Computational Geometry: Theory and Applications, v.8 n.6, p.299-316, Nov. 1997 [doi>10.1016/S0925-7721(96)00027-2 ]
• 15: J. S. B. Mitchell, D. M. Mount, and S. Suri. Query-sensitive ray shooting. International Journal of Computational Geometry and Applications, 7(4):317--347, 1997.
• 16: Shai Mohaban , Micha Sharir, Ray Shooting Amidst Spheres in Three Dimensions and Related Problems, SIAM Journal on Computing, v.26 n.3, p.654-674, June 1997 [doi>10.1137/S0097539793252080]
• 17: Mark H. Overmars , A. Frank van der Stappen, Range Searching and Point Location among Fat Objects, Proceedings of the Second Annual European Symposium on Algorithms, p.240-253, September 26-28, 1994
• 18: M. Pellegrini. Ray shooting on triangles in 3-space. Algorithmica, 9:471--494, 1993.
• 19: Marco Pellegrini, Ray shooting and lines in space, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 20: Otfried Schwarzkopf , Jules Vleugels, Range searching in low-density environments, Information Processing Letters, v.60 n.3, p.121-127, Nov. 11, 1996 [doi>10.1016/S0020-0190(96)00154-8 ]
• 21: M. Sharir and H. Shaul. Ray shooting and stone throwing. In Proc. 11th European Symposium on Algorithms, pages 470--481. Springer-Verlag, LNCS 2832, 2003.
• 22: Micha Sharir , Hayim Shaul, Ray shooting amid balls, farthest point from a line, and range emptiness searching, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 23: A. F. van der Stappen. Motion Planning Amidst Fat Obstacles. PhD thesis, Dept. of Computer Science, Utrecht University, 1994.

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, Theory

Keywords:
computational geometry, fat objects, intersection searching, ray shooting