Vertical ray shooting for fat objects

ABSTRACT

We describe a data structure for vertical ray shooting in a set of n convex fat polyhedra of constant complexity in 3-space. The structure has O(log² n) query time, and it uses O(n log³ n(log log n)²) storage. It can also be used for fat objects with curved boundaries, at the cost of a small increase in storage.

REFERENCES

• 1: P. K. Agarwal and J. Matoušek. On range-searching with semi-algebraic sets. Discr. Comput. Geom. 11: 393--418 (1993).
• 2: Mark de Berg, Ray Shooting, Depth Orders and Hidden Surface Removal, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 3: M. de Berg, M. Katz, F. van der Stappen, and J. Vleugels. Realistic input models for geometric algorithms. Algorithmica 34:81--97 (2002).
• 4: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 5: M. de Berg and M. Streppel. Approximate range searching using binary space partitions. To appear in Proc. IARCS Conf. Found. Software Tech. Theoret. Comput. Sci. (FSTTCS), 2004.
• 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: Alon Efrat, The complexity of the union of (&agr;, &bgr;)-covered objects, Proceedings of the fifteenth annual symposium on Computational geometry, p.134-142, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304958]
• 9: Alon Efrat , Micha Sharir, On the complexity of the union of fat objects in the plane, Proceedings of the thirteenth annual symposium on Computational geometry, p.104-112, June 04-06, 1997, Nice, France [doi>10.1145/262839.262911]
• 10: Alon Efrat , Matthew J. Katz, On the union of κ-curved objects, Proceedings of the fourteenth annual symposium on Computational geometry, p.206-213, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276908]
• 11: M. J. Katz. Personal communication.
• 12: 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]
• 13: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 14: D. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput. 12:28--35 (1983).
• 15: Marc van Kreveld, On fat partitioning, fat covering and the union size of polygons, Computational Geometry: Theory and Applications, v.9 n.4, p.197-210, March 1998 [doi>10.1016/S0925-7721(96)00016-8]
• 16: Jiri Matousek , Janos Pach , Micha Sharir , Shmuel Sifrony , Emo Welzl, Fat Triangles Determine Linearly Many Holes, SIAM Journal on Computing, v.23 n.1, p.154-169, Feb. 1994 [doi>10.1137/S009753979018330X]
• 17: János Pach , Gábor Tardos, On the Boundary Complexity of the Union of Fat Triangles, SIAM Journal on Computing, v.31 n.6, p.1745-1760, 2002 [doi>10.1137/S0097539700382169]
• 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: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 21: A. F. van der Stappen. Motion planning amidst fat obstacles. Ph.D. thesis, Utrecht University, Utrecht, the Netherlands, 1994.
• 22: A. Frank van der Stappen , Dan Halperin , Mark H. Overmars, The complexity of the free space for a robot moving amidst fat obstacles, Computational Geometry: Theory and Applications, v.3 n.6, p.353-373, Dec. 1993 [doi>10.1016/0925-7721(93)90007-S]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

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

General Terms:
Algorithms, Theory

Keywords:
fat objects, geometric data structures, ray shooting, realistic input models