Vertical decomposition of a single cell in a three-dimensional arrangement of surfaces and its applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Vertical decomposition of a single cell in a three-dimensional arrangement of surfaces and its applications

Full text

Pdf (1.10 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 20 - 29

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Otfried Schwarzkopf	Dept. of Computer Science, Pohang University of Science and Technology, San 31, Hyoja-Dong, Pohang 790-784, South Korea
Micha Sharir	School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel, and Courant Institute of Mathematical, Sciences, New York University, New York, NY

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

Additional Information:

references 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/237218.237230 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, O. Schwarzkopf and M. Sharir, The overlay of lower envelopes in three dimensions and its applications, Discrete Comput. Geom. 15 (1996), 1-13.
	2	P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
	3	B. Aronov and M. Sharir, Triangles in space, or: Building (and analyzing) castles in the air, Combinatorica 10 (2) (1990), 137-173.
	4	B. Aronov and M. Sharir, Castles in the air revisited, Discrete Comput. Geom. 12 (1994), 119-150.
	5	Boris Aronov , Micha Sharir, On translational motion planning in 3-space, Proceedings of the tenth annual symposium on Computational geometry, p.21-30, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177445]
	6	M. de Berg, K. Dobrindt and O. Schwarzkopf, On lazy randomized incremental construction, Discrete Comput. Geom. 14 (1995), 261-286.
	7	Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, v.84 n.1, p.77-105, July 22, 1991 [doi>10.1016/0304-3975(91)90261-Y]
	8	Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
	9	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]
	10	D. Halperin and M. Sharir, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Discrete Comput. Geom. 12 (1994), 313-326.
	11	D. Halperin and M. Sharir, Almost tight upper bounds for the single cell and zone problems in three dimensions, Discrete Comput. Geom. 14 (1995), 385-410.
	12	D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment, Proc. 3Jth IEEE Symp. on Foundations of Computer Science, 1993, pp. 382- 391. (Also to appear in Discrete Comput. Geom.)
	13	Dan Halperin , Micha Sharir, Arrangements and their applications in robotics: recent developments, Proceedings of the workshop on Algorithmic foundations of robotics, p.495-511, May 1995, San Francisco, California, United States
	14	S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
	15	M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete Comput. Geom. 6 (1991), 593- 613.
	16	M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions, Discrete Comput. Geom. 12 (1994), 327-345.
	17	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
	18	Boaz Tagansky, A new technique for analyzing substructures in arrangements, Proceedings of the eleventh annual symposium on Computational geometry, p.200-210, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220301]