S Maddila
ABSTRACT
We consider the problem of moving an n vertex simple polygon around a corner in a right-angular corridor. We give an Ο(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 Ο(n2) time algorithm.
- 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.Google Scholar
- 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.Google Scholar
- S82.O. Strang, "The width of a Chair," Atom. Math. Monthly, vol. 89, pp. 529-535, 1982.Google ScholarCross Ref
- Y84.C.K. Yap, "How to move a chair through a door," Courant Institute Technical Report, 1984.Google Scholar
- 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.Google Scholar
Index Terms
- Moving a polygon around the corner in a corridor
Recommendations
Improved algorithm for the widest empty 1-corner corridor
Given a set P of n points on a 2D plane, an empty corridor is an open region bounded by two parallel polygonal chains that does not contain any point of P, and partitions the point-set P into two non-empty parts. An empty corridor is said to be a 1-...
On finding a widest empty 1-corner corridor
A 1-corner corridor through a set S of points is an open subset of CH(S) containing no points from S and bounded by a pair of parallel polygonal lines each of which contains two segments. Given a set of n points in the plane, we consider the problem of ...
Widest-corridor problems
A k-dense corridor through a finite set, S, of n points in the plane is the open region of the plane that is bounded by two parallel lines that intersect the convex hull of S and such that the region contains k points of S. The problem of finding a ...
Comments