Loading...
Please wait, while we are loading the content...
Similar Documents
A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment (1995).
| Content Provider | CiteSeerX |
|---|---|
| Author | Halperin, Dan Sharir, Micha |
| Abstract | We consider the problem of planning the motion of an arbitrary k-sided polygonal robot B, free to translate and rotate in a polygonal environment V bounded by n edges. We present an algorithm that constructs a single component of the free configuration space of B in time O((kn) 2+" ), for any " ? 0. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion planning problem, within the same running time. 1 Introduction Let B be an arbitrary polygonal object with k sides, and let V be an open planar polygonal region bounded by n edges. The configuration space C of B is a 3dimensional parametric space, each point of which represents a possible placement of B by the parameterization (x; y; `), where (x; y) are the coordinates of some fixed Work on this paper by Dan Halperin has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Gran... |
| File Format | |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Polygonal Environment Near-quadratic Algorithm Configuration Space Single Component Motion Planning Open Planar Polygonal Region Nsf Arpa Gran Arbitrary Polygonal Object Possible Placement Rothschild Postdoctoral Fellowship Arbitrary K-sided Polygonal Robot Free Configuration Space Introduction Let Stanford Integrated Manufacturing Association 3dimensional Parametric Space Underlying Motion Planning Problem Running Time Fixed Work Standard Technique |
| Content Type | Text |
| Resource Type | Article |
