Local polyhedra and geometric graphs

ABSTRACT

We introduce a new realistic input model for geometric graphs and nonconvex polyhedra. A geometric graph G is local if (1) the longest edge at every vertex v is only a constant factor longer than the distance from v to its Euclidean nearest neighbor and (2) the lengths of the longest and shortest edges differ by at most a polynomial factor. A polyhedron is local if all its faces are simplices and its edges form a local geometric graph. We show that any boolean combination of any two local polyhedra in IR^d, each with n vertices, can be computed in O(n log n) time, using a standard hierarchy of axis-aligned bounding boxes. Using results of de Berg, we also show that any local polyhedron in IR^d has a binary space partition tree of size O(n log^d-1 n). Finally, we describe efficient algorithms for computing Minkowski sums of local polyhedra in two and three dimensions.

REFERENCES

• 1: G. Barequet, B. Chazelle, L. Guibas, J. Mitchell, and A. Tal. BOXTREE: A hierarchical representation for surfaces in 3D. Comput. Graph. Forum 15(3):C387--C396, C484, 1996. Proc. Eurographics'96.
• 2: M. de Berg. Linear size binary space partitions for uncluttered scenes. Algorithmica 28:353--366, 2000.
• 3: Mark de Berg , Matthew J. Katz , Mark H. Overmars , A. Frank van der Stappen , Jules Vleugels, Models and Motion Planning, Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, p.83-94, July 08-10, 1998
• 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: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 6: Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM Journal on Computing, v.13 n.3, p.488-507, August 1984 [doi>10.1137/0213031]
• 7: B. Chazelle, H. Edelsbrunner, L. J. Guibas, and M. Sharir. Algorithms for bichromatic line segment problems and polyhedral terrains. Algorithmica 11:116--132, 1994.
• 8: Norman Chin , Steven Feiner, Near real-time shadow generation using BSP trees, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.99-106, July 1989
• 9: Norman Chin , Steven Feiner, Fast object-precision shadow generation for area light sources using BSP trees, Proceedings of the 1992 symposium on Interactive 3D graphics, p.21-30, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147159]
• 10: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 11: J. Erickson. On the relative complexities of some geometric problems. Proc. 7th Canad. Conf. Comput. Geom., 85--90, 1995. http://www.uiuc.edu/~jeffe/pubs/relative.html.
• 12: J. Erickson. New lower bounds for Hopcroft's problem. Discrete Comput. Geom. 16:389--418, 1996.
• 13: Jeff Erickson, Nice point sets can have nasty Delaunay triangulations, Proceedings of the seventeenth annual symposium on Computational geometry, p.96-105, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378636]
• 14: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.124-133, July 14-18, 1980, Seattle, Washington, United States
• 15: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 16: Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Proceedings of the eighteenth annual symposium on Computational geometry, p.33-42, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513405]
• 17: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 18: Herman J. Haverkort , Mark de Berg , Joachim Gudmundsson, Box-trees for collision checking in industrial installations, Proceedings of the eighteenth annual symposium on Computational geometry, p.53-62, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513407]
• 19: Philip M. Hubbard, Approximating polyhedra with spheres for time-critical collision detection, ACM Transactions on Graphics (TOG), v.15 n.3, p.179-210, July 1996 [doi>10.1145/231731.231732]
• 20: James T. Klosowski , Martin Held , Joseph S. B. Mitchell , Henry Sowizral , Karel Zikan, Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs, IEEE Transactions on Visualization and Computer Graphics, v.4 n.1, p.21-36, January 1998 [doi>10.1109/2945.675649]
• 21: Xiang-Yang Li , Shang-Hua Teng, Generating well-shaped Delaunay meshed in 3D, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.28-37, January 07-09, 2001, Washington, D.C., United States
• 22: Itay Lotan , Fabian Schwarzer , Dan Halperin , Jean-Claude Latombe, Efficient maintenance and self-collision testing for Kinematic Chains, Proceedings of the eighteenth annual symposium on Computational geometry, p.43-52, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513406]
• 23: Gary L. Miller , Dafna Talmor , Shang-Hua Teng , Noel Walkington, A Delaunay based numerical method for three dimensions: generation, formulation, and partition, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.683-692, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225286]
• 24: Brian Mirtich , John Canny, Impulse-based dynamic simulation, Proceedings of the workshop on Algorithmic foundations of robotics, p.407-418, May 1995, San Francisco, California, United States
• 25: T. M. Murali , Thomas A. Funkhouser, Consistent solid and boundary representations from arbitrary polygonal data, Proceedings of the 1997 symposium on Interactive 3D graphics, p.155-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253326]
• 26: Bruce Naylor , John Amanatides , William Thibault, Merging BSP trees yields polyhedral set operations, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.115-124, Aug. 1990
• 27: P. van Oosterom. An R-tree based map-overlay algorithm. Proc. EGIS '94, 318--327, 1994.
• 28: Mark H. Overmars , A. Frank van der Stappen, Range searching and point location among fat objects, Journal of Algorithms, v.21 n.3, p.629-656, Nov. 1996 [doi>10.1006/jagm.1996.0063]
• 29: 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]
• 30: Michael S. Paterson , F. Frances Yao, Optimal binary space partitions for orthogonal objects, Journal of Algorithms, v.13 n.1, p.99-113, March 1992 [doi>10.1016/0196-6774(92)90007-Y]
• 31: M. Pellegrini. Ray shooting on triangles in 3-space. Algorithmica 9:471--494, 1993.
• 32: 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]
• 33: Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
• 34: A. F. van~der Stappen. Motion Planning amidst Fat Obstacles. Ph.D. dissertation, Dept. Comput. Sci., Utrecht Univ., Utrecht, Netherlands, 1994.
• 35: Subhash Suri , Philip M. Hubbard , John F. Hughes, Collision detection in aspect and scale bounded polyhedra, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.127-136, January 25-27, 1998, San Francisco, California, United States
• 36: Elmar Schömer , Christian Thiel, Efficient collision detection for moving polyhedra, Proceedings of the eleventh annual symposium on Computational geometry, p.51-60, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220285]
• 37: R. A. Schumacker, R. Brand, M. Gilliland, and W. Sharp. Study for applying computer-generated images to visual simulation. Tech. Rep. AFHRL--TR--69--14, U.S. Air Force Human Resources Laboratory, 1969.
• 38: D. Talmor. Well-Spaced Points and Numerical Methods. Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, August 1997. http://reports-archive.adm.cs.cmu.edu/anon/1997/abstracts/97-164.html. Technical report CMU-CS-97-164.
• 39: Seth J. Teller , Carlo H. Séquin, Visibility preprocessing for interactive walkthroughs, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.61-70, July 1991
• 40: Shang-Hua Teng, Points, spheres, and separators: a unified geometric approach to graph partitioning, Carnegie Mellon University, Pittsburgh, PA, 1992
• 41: William C. Thibault , Bruce F. Naylor, Set operations on polyhedra using binary space partitioning trees, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.153-162, July 1987
• 42: J. Vleugels. On Fatness and Fitness --- Realistic Input Models for Geometric Algorithms. Ph.D. thesis, Dept. Comput. Sci., Univ. Utrecht, Utrecht, The Netherlands, 1997.
• 43: Yunhong Zhou , Subhash Suri, Analysis of a bounding box heuristic for object intersection, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.830-839, January 17-19, 1999, Baltimore, Maryland, United States
• 44: Afra Zomorodian , Herbert Edelsbrunner, Fast software for box intersections, Proceedings of the sixteenth annual symposium on Computational geometry, p.129-138, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336192]

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

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

General Terms:
Algorithms, Theory

Keywords:
binary space partition, bounding volume hierarchies, collision detection, realistic input models