Moving a polygon around the corner in a corridor

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Moving a polygon around the corner in a corridor

Full text

Pdf (494 KB)

Source

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

Yorktown Heights, New York, United States

Pages: 187 - 192

Year of Publication: 1986

ISBN:0-89791-194-6

Authors

S Maddila	Coordinated Science Laboratory, Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL
C K Yap	Courant Institute of Mathematical Sciences, New York University, 251, Mercer Street, 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): 0, Downloads (12 Months): 9, Citation Count: 2

Additional Information:

abstract 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/10515.10536 What is a DOI?

ABSTRACT

We consider the problem of moving an n vertex simple polygon around a corner in a right-angular corridor. We give an &Ogr;(n log n) algorithm for a convex polygon which constructs a motion of the polygon when one exists; otherwise it reports that none exists. In the case of non-convex polygons, we have an &Ogr;(n2) time algorithm.

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.

	B82	R.A. Brooks, "Solving the find-path problem by representing free space as generalized cones," IFFFTrans. Systems, Man and Cybernetics, vol. SMC-i3, no. 2, pp. 190-197, 1983.
	M86	S.R. Maddila, "Decomposition algorithm for moving a Ladder among Rectangular Obstacles," Proc. of IFF~ Inter. Conf. on Robotics and Automation, San Francisco, April, 1986.
	S82	O. Strang, "The width of a Chair," Atom. Math. Monthly, vol. 89, pp. 529-535, 1982.
	Y84	C.K. Yap, "How to move a chair through a door," Courant Institute Technical Report, 1984.
	Y85	C.K. Yap, "Algorithmic motion planning," in Advances in Robotics, Votwne I: algorithmic and eleometr/c issues, ed. J.T. Schwartz and C.K. Yap, Lawrence Erlbaum Associates, 1985.

CITED BY 2

	Eric Monfroy , Michaël Rusinowitch , René Schott, Implementing non-linear constraints with cooperative solvers, Proceedings of the 1996 ACM symposium on Applied Computing, p.63-72, February 17-19, 1996, Philadelphia, Pennsylvania, United States
	P. Agarwal , M. Sharir, Red-Blue intersection detection algorithms, with applications to motion planning and collision detection, Proceedings of the fourth annual symposium on Computational geometry, p.70-80, June 06-08, 1988, Urbana-Champaign, Illinois, United States