Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
It is proposed to estimate time complexity of motion planning algorithms in terms of both the problem size and the tightness parameter; the latter is intuitively the amount of scaling of the movable object which turns the problem from solvable to unsolvable or conversely. An algorithm for motion planning of the rectangle in the plane amidst polygonal obstacles with the complexity \(O(((a/b)(1/t)+1)n\log^ 2 n)\) is proposed, where \(t\) is for tightness. For ``non-tight problems, this significantly improves the known \(\Omega(n^ 2)\) upper bounds. As a technical contribution, the complexities of boundaries of unions of some simple figures are presented. This leads to \(O((1/a)n\log^ 2 n)\) motion planning for a rectangle which may be rotated by angles less than \(a\).
- A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
- scientific article; zbMATH DE number 3945381
- Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
- Motion planning in the presence of moving obstacles
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
- On the general motion-planning problem with two degrees of freedom
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Optimal Point Location in a Monotone Subdivision
- Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- On \(k\)-sets in arrangements of curves and surfaces
- Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
- Simultaneous inner and outer approximation of shapes
- The complexity of the free space for a robot moving amidst fat obstacles
- 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
- On fat partitioning, fat covering and the union size of polygons
- Models and motion planning
- On the union complexity of families of axis-parallel rectangles with a low packing number
- The complexity of the free space for motion planning amidst fat obstacles
- On the flatness of Minkowski sums
- Computing depth orders for fat objects and related problems
- A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment
- Geometric eccentricity and the complexity of manipulation plans
- Visibility of rectagular objects inL1metric
- Models and motion planning
- Two- and three- dimensional point location in rectangular subdivisions
- Computing depth orders and related problems
- Dynamic data structures for fat objects and their applications
- On complexity and motion planning for co-rank one sub-Riemannian metrics
- Generalized disk graphs
- An optimal-time algorithm for shortest paths on realistic polyhedra
- On realistic terrains
- Improved bounds on the union complexity of fat objects
This page was built for publication: Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201745)
