A new technique for analyzing substructures in arrangements

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new technique for analyzing substructures in arrangements

Full text

Pdf (1.19 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: 200 - 210

Year of Publication: 1995

ISBN:0-89791-724-3

Author

Boaz Tagansky

School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel

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): 10, Citation Count: 2

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.220301 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	Pankaj K. Agarwal , Boris Aronov, Counting facets and incidences, Discrete & Computational Geometry, v.7 n.4, p.359-369, 1992 [doi>10.1007/BF02187848]
	2	P.K. Agarwal, O. Schwarzkopf and M. Sharir, The overlay of lower envelopes in three dlmensions and its applications, Manuscript, 1994.
	3	Boris Aronov , Marco Pellegrini , Micha Sharir, On the zone of a surface in a hyperplane arrangement, Discrete & Computational Geometry, v.9 n.2, p.177-186, 1993 [doi>10.1007/BF02189317]
	4	B. Aronov and M. Sharir, Triangles in space, or: Building (and analyzing) castles in the air, Combi, atoric4 10 (2) (1990), 137-173.
	5	B. Aronov and M. Sharir, Castles in the air revisited, Discrete Comput. Geom. 12 (1994), 119-150.
	6	Boris Aronov , Micha Sharir , Boaz Tagansky, The Union of Convex Polyhedra in Three Dimensions, SIAM Journal on Computing, v.26 n.6, p.1670-1688, Dec. 1997 [doi>10.1137/S0097539793250755]
	7	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]
	8	Jean-Daniel Boissonnat , Micha Sharir , Boaz Tagansky , Mariette Yvinec, Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Proceedings of the eleventh annual symposium on Computational geometry, p.79-88, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220288]
	9	L. Paul Chew , Klara Kedem , Micha Sharir , Boaz Tagansky , Emo Welzl, Voronoi diagrams of lines in 3-space under polyhedral convex distance functions, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.197-204, January 22-24, 1995, San Francisco, California, United States
	10	K. Clarkson, New applications of random sampling in computational geometry, Discrete Comp~t. Geom. 2 (1987), 195- 222.
	11	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]
	12	Mark de Berg , Katrin Dobrindt , Otfried Schwarzkopf, On lazy randomized incremental construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.105-114, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195113]
	13	Marc de Berg , Leonidas J. Guibas , Dan Halperin, Vertical decompositions for triangles in 3-space, Proceedings of the tenth annual symposium on Computational geometry, p.1-10, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177427]
	14	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	15	H. Edelsbrunner, The upper envelope of piecewise linear functions: Tight bounds on the number of faces, Discrete Comput. Geom. 4 (1989), 337-343.
	16	Herbert Edelsbrunner , Raimund Seidel , Micha Sharir, On the zone theorem for hyperplane arrangements, SIAM Journal on Computing, v.22 n.2, p.418-429, April 1993 [doi>10.1137/0222031]
	17	L. Guibas, D. Halperin, J. M&touiek and M. Sharir, On vextical decomposition of arrangements of hyperplanes in four dimensions, to appear in Discrete Comput. Geom.
	18	L. Guibas and M. Shark, Combinatorlcs and algorithms of arrangements, in New Trends in Discrete and Compstatio~al Geomet~, (J. Pach, Ed.), $pringer-Vexlag, 1993, 9-36.
	19	D. Halperin and M. Sharir, New bounds for lower envelopes in three dimensions with applications to visibility of terrains, Discrete Comput. Geom. 12 (1994), 313--326.
	20	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
	21	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]
	22	K. Mulmuley, Computations! Geometry: Introduction tkrougk Randomized Algorithms, Prentice Hall, New York, 1993.
	23	J. Pach and M. Sharir, The upper envelope of plecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis, Discrete Comp~t. Geom. 4 (19S9), 291-309.
	24	M. Sharlr, Almost tight upper bounds for lower envelopes in higher dimensions, Discrete Comput. Geom. 12 (1994), 327- 345.
	25	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
	26	Ady Wiernik , Micha Sharir, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete & Computational Geometry, v.3 n.1, p.15-47, Jan., 1988 [doi>10.1007/BF02187894]

CITED BY 2

	Jean-Daniel Boissonnat , Micha Sharir , Boaz Tagansky , Mariette Yvinec, Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Proceedings of the eleventh annual symposium on Computational geometry, p.79-88, June 05-07, 1995, Vancouver, British Columbia, Canada
	Otfried Schwarzkopf , Micha Sharir, Vertical decomposition of a single cell in a three-dimensional arrangement of surfaces and its applications, Proceedings of the twelfth annual symposium on Computational geometry, p.20-29, May 24-26, 1996, Philadelphia, Pennsylvania, United States