Planar Motion Planning (Motion Planning Problems)

Description

Given a set of non-intersecting, non-touching, axis-parallel line segment obstacles in the plane and a line segment robot (a rod or ladder), determine whether the rod can be moved (allowing both translation and rotation) from a given source to a given goal configuration without colliding with the obstacles.

Related Problems

Related: 3D Motion Planning

Parameters

$n$: number of line segment obstacles

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
GeomBase	if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$ then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$	1995	https://doi.org/10.1016/0925-7721(95)00022-2	link

References/Citation

https://link.springer.com/content/pdf/10.1007/3-540-52846-6_81.pdf