Box-trees for collision checking in industrial installations

ABSTRACT

A box-tree is a bounding-volume hierarchy that uses axis-aligned boxes as bounding volumes. We describe a new algorithm to construct a box-tree for a 3D scene consisting of n objects, and we analyze its worst-case query time for approximate range queries. If the input scene has certain characteristics that we derived from our application---collision detection in industrial installations---then the query times are polylogarithmic, not only for searching with boxes but also for range searching with other constant-complexity ranges.

REFERENCES

• 1: Pankaj K. Agarwal , Mark de Berg , Joachim Gudmundsson , Mikael Hammar , Herman J. Haverkort, Box-trees and R-trees with near-optimal query time, Proceedings of the seventeenth annual symposium on Computational geometry, p.124-133, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378645]
• 2: N. Amato and Y. Wu. A randomized roadmap method for path and manipulation planning. In Proc. IEEE Int. Conf. Robot. Autom., pages 113--120, 1996.
• 3: Sunil Arya , David M. Mount, Approximate range searching, Computational Geometry: Theory and Applications, v.17 n.3-4, p.135-152, Dec. 2000 [doi>10.1016/S0925-7721(00)00022-5]
• 4: Mark de Berg , Matthew Katz , A. Frank van der Stappen , Jules Vleugels, Realistic input models for geometric algorithms, Proceedings of the thirteenth annual symposium on Computational geometry, p.294-303, June 04-06, 1997, Nice, France [doi>10.1145/262839.262986]
• 5: Matthew Dickerson , Christian A. Duncan , Michael T. Goodrich, K-D Trees Are Better when Cut on the Longest Side, Proceedings of the 8th Annual European Symposium on Algorithms, p.179-190, September 05-08, 2000
• 6: Christian Alexander Duncan , Michael T. Goodrich, Balanced aspect ratio trees, 2000
• 7: Christian A. Duncan , Michael T. Goodrich , Stephen Kobourov, Balanced aspect ratio trees: combining the advantages of k-d trees and octrees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.300-309, January 17-19, 1999, Baltimore, Maryland, United States
• 8: Lydia E. Kavraki, Random networks in configuration space for fast path planning, Stanford University, Stanford, CA, 1995
• 9: MOLOG: Motion for Logistics. Esprit LTR Project 28226. http://www.laas.fr/molog/
• 10: A.F. van der Stappen, M.H. Overmars, M. de Berg, and J. Vleugels. Motion planning in environments with low obstacle density. Discrete Comput. Geom. 20:561--587 (1998).
• 11: P. Švestka. Robot motion planning using probabilistic roadmaps. PhD thesis, Utrecht University, 1997.

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Object hierarchies

General Terms:
Algorithms, Theory

Keywords:
bounding-volume hierarchy, box-tree, orthogonal range query, slicing number, window query