Stabbing triangulations by lines in 3D

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Stabbing triangulations by lines in 3D

Full text

Pdf (1.11 MB)

Source

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

Vancouver, British Columbia, Canada

Pages: 267 - 276

Year of Publication: 1995

ISBN:0-89791-724-3

Authors

Pankaj K. Agarwal	Department of Computer Science, Box 90129, Duke University, Durham, NC
Boris Aronov	Computer Science Department, Polytechnic University, Six MetroTech Center, Brooklyn, NY
Subhash Suri	Department of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MO

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): 4, Downloads (12 Months): 26, Citation Count: 6

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/220279.220308 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	B. Aronov and J. Matou~ek. On stabbing triangles by lines in 3-space. Commentationes Mathematicae Universitatis Carolinae, to appear.
	2	B. Aronov and M. Sharir, Triangles in space, or building (and analyzing) castles in the air, Combinato~ 10(2)(1990), 137-173.
	3	M. Bern and D. Eppstein, Mesh generation and optimal triangulation, in: Computing in Euclidean Geometry, (D. Du and F. Hwang, eds.), 1992, World Scientific, Singapore.
	4	Marshall Bern, Compatible tetrahedralizations, Proceedings of the ninth annual symposium on Computational geometry, p.281-288, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161151]
	5	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]
	6	B. Chazelle , H. Edelsbrunner , L. Guibas, The complexity of cutting complexes, Discrete & Computational Geometry, v.4 n.2, p.139-181, Jan. 1989 [doi>10.1007/BF02187720]
	7	Bernard Chazelle , Leonidas Palios, Triangulating a nonconvex polytope, Discrete & Computational Geometry, v.5 n.5, p.505-526, 1990 [doi>10.1007/BF02187807]
	8	Bernard Chazelle , Nadia Shouraboura, Bounds on the size of tetrahedralizations, Proceedings of the tenth annual symposium on Computational geometry, p.231-239, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177975]
	9	B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
	10	David P. Dobkin , David G. Kirkpatrick, Fast Detection of Polyhedral Intersections, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.154-165, July 12-16, 1982
	11	D. Dobkin and D. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra. J. of Algorithms, 6:381-392, 1985.
	12	H. Edelsbrunner. Triangulations. Course Notes CS 497. University of Illinois, Urbana-Champaign, 1991.
	13	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
	14	Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
	15	Joseph S. B. Mitchell , David M. Mount , Subhash Suri, Query-sensitive ray shooting, Proceedings of the tenth annual symposium on Computational geometry, p.359-368, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178094]
	16	Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
	17	J. Ruppert , R. Seidel, On the difficulty of tetrahedralizing 3-dimensional non-convex polyhedra, Proceedings of the fifth annual symposium on Computational geometry, p.380-392, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73875]
	18	E. Welzl. On spanning trees with low crossing numbers. Tech. Rept. B92-02, Free University, Berlin, 1992.

CITED BY 6

	Siu-Wing Cheng , Tamal K. Dey, Approximate minimum weight Steiner triangulation in three dimensions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.205-214, January 17-19, 1999, Baltimore, Maryland, United States
	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
	Boris Aronov , Hervé Brönnimann , Allen Y. Chang , Yi-Jen Chiang, Cost prediction for ray shooting, Proceedings of the eighteenth annual symposium on Computational geometry, p.293-302, June 05-07, 2002, Barcelona, Spain
	Sándor P. Fekete , Marco E. Lübbecke , Henk Meijer, Minimizing the stabbing number of matchings, trees, and triangulations, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Boris Aronov , Hervé Brönnimann , Allen Y. Chang , Yi-Jen Chiang, Cost prediction for ray shooting in octrees, Computational Geometry: Theory and Applications, v.34 n.3, p.159-181, July 2006
	Pankaj K. Agarwal , R. Sharathkumar , Hai Yu, Approximate Euclidean shortest paths amid convex obstacles, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.283-292, January 04-06, 2009, New York, New York