Query-sensitive ray shooting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Query-sensitive ray shooting

Full text

Pdf (1.08 MB)

Source

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

Stony Brook, New York, United States

Pages: 359 - 368

Year of Publication: 1994

ISBN:0-89791-648-4

Authors

Joseph S. B. Mitchell	Applied Math, SUNY, Stony Brook, NY
David M. Mount	Dept. of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD
Subhash Suri	Bellcore, Room 2Q-358, 445 South street, Morristown, NJ

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): 2, Downloads (12 Months): 14, Citation Count: 14

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/177424.178094 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, A deterministic algorithm for partitioning arrangements of lines and its application, Proceedings of the fifth annual symposium on Computational geometry, p.11-22, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73835]
	2	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
	3	Marshall Bern, Approximate closest-point queries in high dimensions, Information Processing Letters, v.45 n.2, p.95-99, Feb. 26, 1993 [doi>10.1016/0020-0190(93)90222-U]
	4	M. Bern, D. Eppstein, and J. Gilbert. Provably good mesh generation. In Proc. 31st Annu. IEEE Sympos. Found. Comput. Sci., pages 231-241, 1990.
	5	Paul B. Callahan , S. Rao Kosaraju, A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.546-556, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129766]
	6	Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , John Hershberger , Micha Sharir , Jack Snoeyink, Ray shooting in polygons using Geodesic triangulations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.661-673, June 1991, Madrid, Spain
	7	Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
	8	Siu Wing Cheng , Ravi Janardan, Space-efficient ray-shooting and intersection searching: algorithms, dynamization, and applications, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.7-16, January 28-30, 1991, San Francisco, California, United States
	9	Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
	10	John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.54-63, January 25-27, 1993, Austin, Texas, United States
	11	Brian Von Herzen , Alan H. Barr, Accurate triangulations of deformed, intersecting surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.103-110, July 1987
	12	J.S.B. Mitchell. Computational geometry methods for virtual reality. Manuscript, Applied Math, SUNY Stony Brook, 1993.
	13	Scott A. Mitchell , Stephen A. Vavasis, Quality mesh generation in three dimensions, Proceedings of the eighth annual symposium on Computational geometry, p.212-221, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142720]
	14	Douglas William Moore, Simplicial mesh generation with applications, Cornell University, Ithaca, NY, 1992
	15	M. H. Overmars , H. Schipper , M. Sharir, Storing line segments in partition trees, BIT, v.30 n.3, p.385-403, 1990 [doi>10.1007/BF01931656]
	16	Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	17	P. M. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete & Computational Geometry, v.4 n.2, p.101-115, Jan. 1989 [doi>10.1007/BF02187718]

CITED BY 14

	Cláudio Silva , Joseph S. B. Mitchell , Arie E. Kaufman, Fast rendering of irregular grids, Proceedings of the 1996 symposium on Volume visualization, p.15-ff., October 28-29, 1996, San Francisco, California, United States
	Martin Held , James T. Klosowski , Joseph S. B. Mitchell, Collision detection for fly-throughs in virtual environments, Proceedings of the twelfth annual symposium on Computational geometry, p.513-514, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	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
	Doug Moore, The cost of balancing generalized quadtrees, Proceedings of the third ACM symposium on Solid modeling and applications, p.305-312, May 17-19, 1995, Salt Lake City, Utah, United States
	Jeff Erickson , Leonidas J. Guibas , Jorge Stolfi , Li Zhang, Separation-sensitive collision detection for convex objects, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.327-336, January 17-19, 1999, Baltimore, Maryland, United States
	Danny Z. Chen, On the all-pairs Euclidean short path problem, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.292-301, January 22-24, 1995, San Francisco, California, United States
	Sunil Arya , Siu-Wing Cheng , David M. Mount, Approximation algorithms for multiple-tool miling, Proceedings of the fourteenth annual symposium on Computational geometry, p.297-306, June 07-10, 1998, Minneapolis, Minnesota, United States
	F. Cazals , C. Puech, Bucket-like space partitioning data structures with applications to ray-tracing, Proceedings of the thirteenth annual symposium on Computational geometry, p.11-20, June 04-06, 1997, Nice, France
	Pankaj K. Agarwal , Boris Aronov , Subhash Suri, Stabbing triangulations by lines in 3D, Proceedings of the eleventh annual symposium on Computational geometry, p.267-276, June 05-07, 1995, Vancouver, British Columbia, Canada
	Cláudio T. Silva , Joseph S. B. Mitchell , Peter L. Williams, An exact interactive time visibility ordering algorithm for polyhedral cell complexes, Proceedings of the 1998 IEEE symposium on Volume visualization, p.87-94, October 19-20, 1998, Research Triangle Park, North Carolina, United States
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	Boris Aronov , Steven Fortune, Average-case ray shooting and minimum weight triangulations, Proceedings of the thirteenth annual symposium on Computational geometry, p.203-211, June 04-06, 1997, Nice, France
	James T. Klosowski , Cláudio T. Silva, The Prioritized-Layered Projection Algorithm for Visible Set Estimation, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.108-123, April 2000
	Claudio T. Silva , Joseph S. B. Mitchell, The Lazy Sweep Ray Casting Algorithm for Rendering Irregular Grids, IEEE Transactions on Visualization and Computer Graphics, v.3 n.2, p.142-157, April 1997