Cylindrical static and kinetic binary space partitions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cylindrical static and kinetic binary space partitions

Full text

Pdf (1.34 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the thirteenth annual symposium on Computational geometry table of contents

Nice, France

Pages: 39 - 48

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Pankaj K. Agarwal	Center for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC
Leonidas J. Guibas	Graphics Laboratory, Computer Science Department, Gates Building 3B, Room 374, Stanford University, Stanford, CA
T. M. Murali	Center for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC
Jeffrey Scott Vitter	Center for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 14, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/262839.262858 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. K. Agarwal, J. Erickson, and L. J. Guibas, Kinetic binary space partitions in R3, In preparation, 1997.
	2	P. K. Agarwal , E. F. Grove , T. M. Murali , J. S. Vitter, Binary space partitions for fat rectangles, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.482, October 14-16, 1996
	3	Pankaj K. Agarwal , Subhash Suri, Surface approximation and geometric partitions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.24-33, January 23-25, 1994, Arlington, Virginia, United States
	4	John Milligan Airey , Frederick P. Brooks, Jr., Increasing update rates in the building walkthrough system with automatic model-space subdivision and potentially visible set calculations, 1990
	5	C. Ballieux, Motion planning using binary space partitions, Tech. Rep. inf/src/93-25, Utrecht University, 1993.
	6	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
	7	Alvin Theophilus Campbell, III, Modeling global diffuse illumination for image synthesis, University of Texas at Austin, Austin, TX, 1992
	8	T. Cassen, K. R. Subramanian, and Z. Michalewicz, Near-optimal construction of partitioning trees by evolutionary techniques, Proc. of Graphics Interface '95, 1995, pp. 263-271.
	9	Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
	10	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
	11	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]
	12	Y. Chrysanthou, Shadow Computation for 3D Interaction and Animation, Ph.D. Thesis, Queen Mary and Westfield College, University of London, 1996.
	13	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]
	14	Mark de Berg, Linear Size Binary Space Partitions for Fat Objects, Proceedings of the Third Annual European Symposium on Algorithms, p.252-263, September 25-27, 1995
	15	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	16	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
	17	D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2 (1987), 127- 151.
	18	Cristian S. Mata , Joseph S. B. Mitchell, Approximation algorithms for geometric tour and network design problems (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.360-369, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220318]
	19	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]
	20	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
	21	B. Naylor and W. Thibault, Application of BSP trees to ray-tracing and CSG evaluation, Technical Report GIT-ICS 86/03, Georgia Institute of Tech., School of Information and Computer Science, 1986.
	22	B. Naylor, SCULPT: an interactive solid modeling tool, Proceedings on Graphics interface '90, p.138-148, June 1990, Halifax, Nova Scotia
	23	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
	24	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]
	25	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]
	26	R. A. Schumacker, R. Brand, M. Gilliland, and W. Sharp, Study for #pplying computer-generated images to visual simulation, Tech. Rep. AFHRL-TR-69- 14, U.S. Air Force Human Resources Laboratory, 1969.
	27	R. Seidel, Backwards analysis of randomized geometric algorithms, in: New Trends in Discrete and Computational Geometry (J. Pach, ed.), Algorithms and Combinatorics, Vol. 10, Springer-Verlag, 1993, pp. 37-68.
	28	Seth Jared Teller, Visibility computations in densely occluded polyhedral environments, University of California at Berkeley, Berkeley, CA, 1992
	29	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
	30	E. Torres, Optimization of the binary space partition algorithm (BSP) for the. visualization of dynamic scenes, Eurographics '90, North-Holland, 1990, pp. 507-518.

CITED BY 3

	Mark de Berg , Joao Comba , Leonidas J. Guibas, A segment-tree based kinetic BSP, Proceedings of the seventeenth annual symposium on Computational geometry, p.134-140, June 2001, Medford, Massachusetts, United States
	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
	Marina L. Gavrilova, Empirical Studies of Optimization Techniques in the Event-Driven Simulation of Mechanically Alloyed Materials, The Journal of Supercomputing, v.28 n.2, p.165-176, May 2004