A segment-tree based kinetic BSP

ABSTRACT

We present anew technique to maintain a BSP for a set of n moving disj oint segments in the plane. Our kinetic BSP uses O(n log n) storage and it undergoes O(n 2 ) changes in the worst case, assuming that the endpoints of the segments move along bounded-degree algebraically dened trajecto- ries. The response time (the time needed to update the BSP when it undergoes a change) is O(log 2 n). A random- ized variant achieves O(log n) expected response time, while the worst-case response time remains O(log 2 n).The new BSP is based on a simple technique for main- taining a 1-d segment tree on a set of intervals on the real line with moving endpoints. The response time of the ki- netic segment treeisO(log n) intheworst case, and O(1) expected.

REFERENCES

• 1: P.K. Agarwal, J. Basch, M. de Berg, L.J. Guibas, and J. Hershberger. Lower bounds for kinetic planar subdivisions. Discrete Comput. Geom., To appear.
• 2: Pankaj K. Agarwal , Jeff Erickson , Leonidas J. Guibas, Kinetic binary space partitions for intersecting segments and disjoint triangles, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.107-116, January 25-27, 1998, San Francisco, California, United States
• 3: Pankaj K. Agarwal , Leonidas J. Guibas , T. M. Murali , Jeffrey Scott Vitter, Cylindrical static and kinetic binary space partitions, Proceedings of the thirteenth annual symposium on Computational geometry, p.39-48, June 04-06, 1997, Nice, France [doi>10.1145/262839.262858]
• 4: C. Ballieux. Motion planning using binary space partitions. Technical Report Inf/src/93-25, Utrecht University, 1993.
• 5: Julien Basch , Leonidas J. Guibas , John Hershberger, Data structures for mobile data, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.747-756, January 05-07, 1997, New Orleans, Louisiana, United States
• 6: M. de Berg. Linear size binary space partitions for uncluttered scenes. Algorithmica, To appear.
• 7: Mark de Berg , Marko de Groot , Mark Overmars, New results on binary space partitions in the plane, Computational Geometry: Theory and Applications, v.8 n.6, p.317-333, Nov. 1997 [doi>10.1016/S0925-7721(97)00008-4]
• 8: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 9: Norman Chin , Steven Feiner, Near real-time shadow generation using BSP trees, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.99-106, July 1989
• 10: 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]
• 11: Y. Chrysanthou. Shadow Computation for 3D Interaction and Animation. Ph.D. thesis, Queen Mary and Westfield College, University of London, 1996.
• 12: Joao Luiz Dihl Comba , Leonidas J. Guibas, Kinetic vertical decomposition trees, 1999
• 13: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 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: L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proc. 19th Annu. IEEE Sympos. Found. Comput. Sci., Lecture Notes Comput. Sci., pages 8-21. Springer-Verlag, 1978.
• 16: 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]
• 17: Bruce F. Naylor, Interactive solid geometry via partitioning trees, Proceedings of the conference on Graphics interface '92, p.11-18, September 1992, Vancouver, British Columbia, Canada
• 18: B. Naylor. Constructing good partitioning trees. In Proc. Graphics Interface '93, pages 181-191, 1993.
• 19: 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
• 20: 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]
• 21: 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]
• 22: F. P. Preparata. A new approach to planar point location. SIAM J. Comput., 10:473-482, 1981.
• 23: 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
• 24: 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
• 25: E. Torres. Optimization of the binary space partition algorithm (BSP) for the visualization of dynamic scenes. In Eurographics '90, pages 507-518. North-Holland, 1990.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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

General Terms:
Design, Theory, Verification