Extremal polygon containment problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Extremal polygon containment problems

Full text

Pdf (1.00 MB)

Source

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

North Conway, New Hampshire, United States

Pages: 176 - 185

Year of Publication: 1991

ISBN:0-89791-426-0

Author

Sivan Toledo

Computer Science Department, Tel Aviv University

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/109648.109668 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.

	AB	F. Avnaim and J. D. Boissonnat, The polygon containment problem: 1. Simultaneous containment under translation, Technical report 689, INRiA Sopfia Antipolis, June 1987.
	AB1	Francis Avnaim , Jean-Daniel Boissonnat, Polygon Placement Under Translation and Rotation, Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science, p.322-333, February 11-13, 1988
	ACGOY	A. Aggarwal, B. Chazelle, L. Guibas, C. 0'D6nlaing and C. Yap, Parallel computational geometry, Algorithmica, 3 (1988), 293-327.
	ASS	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]
	Ch	B. Chazelle, The polygon containment problem, in Advances in Computing Research, Vol I: Computational Geometry, (F.P. Preparata, ed.), j Ai Press, Greenwich, Connecticut (1983), 1-33.
	Ch1	Bernard Chazelle, Reporting and counting segment intersections, Journal of Computer and System Sciences, v.32 n.2, p.156-182, April 1986 [doi>10.1016/0022-0000(86)90025-5]
	CK	L. P. Chew , K. Kedem, Placing the largest similar copy of a convex polygon among polygonal obstacles, Proceedings of the fifth annual symposium on Computational geometry, p.167-173, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73853]
	CK1	L. P. Chew and K. Kedem, High-clearance motion planning for a convex polygon among polygonal obstacles, Technical report 90-1133, Dept. of Computer Science, Cornell University, june 1990.
	Co	R. Cole, Parallel merge sort, ~Tth IEEE Syrup. on Foundations of Computer Science, 1986, 511- 516.
	Ed	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	Fo	Steven Fortune, A Fast Algorithm for Polygon Containment by Translation (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.189-198, July 15-19, 1985
	GRS	L. Guibas, L. Ramshaw and J. Stolfi, A kinetic framework for computational geometry, 2dth iEEE $ymp. on Foundations of Computer Science, 1983, 100-111.
	HS	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]
	KS	K. Kedem , M. Sharir, Planning algorithm for a convex polygonal object in two-dimensional polygonal space, Discrete & Computational Geometry, v.5 n.1, p.43-75, Jan. 1990 [doi>10.1007/BF02187779]
	LS	D. Leven and M. Sharir, On the number of critical free contacts of a convex polygonal object in two-dimensional polygonal space, Discrete and Computational Geometry 2 (1987), 255-270.
	LS1	D. Leven and M. Sharir, Planning a purely translational motion for a convex object in twodimensional space using generalized Voronoi diagrams, Discrete and Computational Geomeiry 2 (1987), 9-31.
	Me	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	PY	M.S. Paterson and F.F. Yao, Point retrieval for polygons, J. Algorithms, 7 (1986), 441-447.
	SS	J.T. Schwartz and M. Sharir, On the Piano Movers Problem: II. General techniques for computing topological properties of real algebraic manifolds, Advances in Applied Mathematics 4 (1983), 298-351.
	Va	L. Valiant, Parallelism in comparison problems, SIAM J. Computing 4 (1975), 345-348.

CITED BY 4

	Matthew J. Katz , Micha Sharir, An expander-based approach to geometric optimization, Proceedings of the ninth annual symposium on Computational geometry, p.198-207, May 18-21, 1993, San Diego, California, United States
	Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, Diameter, width, closest line pair, and parametric searching, Proceedings of the eighth annual symposium on Computational geometry, p.120-129, June 10-12, 1992, Berlin, Germany
	Marco Pellegrini, Incidence and nearest-neighbor problems for lines in 3-space, Proceedings of the eighth annual symposium on Computational geometry, p.130-137, June 10-12, 1992, Berlin, Germany
	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States