On the general motion-planning problem with two degrees of freedom
From MaRDI portal
DOI10.1007/BF02187744zbMATH Open0685.68049OpenAlexW1994094252MaRDI QIDQ1262130FDOQ1262130
Authors: Shmuel Sifrony, Leonidas Guibas, Micha Sharir 
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131093
Recommendations
- On the Piano Movers' problem: IV. Various decomposable two-dimensional motion-planning problems
- Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
- scientific article; zbMATH DE number 3945381
- scientific article; zbMATH DE number 4108220
- On the complexity of a single cell in certain arrangements of surfaces related to motion planning
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Other designs, configurations (05B30) Other problems of combinatorial convexity (52A37)
Cites Work
- Title not available (Why is that?)
- Combinatorial complexity bounds for arrangements of curves and spheres
- Algorithms for Reporting and Counting Geometric Intersections
- An optimal algorithm for intersecting line segments in the plane
- Topologically sweeping an arrangement
- The complexity and construction of many faces in arrangements of lines and of segments
- Visibility and intersection problems in plane geometry
- Some dynamic computational geometry problems
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Implicitly representing arrangements of lines or segments
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
- Separating two simple polygons by a sequence of translations
- Triangles in space or building (and analyzing) castles in the air
- Title not available (Why is that?)
- Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
- A “retraction” method for planning the motion of a disc
- Generalized voronoi diagrams for moving a ladder. I: Topological analysis
- A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
- On arrangements of Jordan arcs with three intersections per pair
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
- On the piano movers' problem: V. The case of a rod moving in three-dimensional space amidst polyhedral obstacles
- An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers
- Title not available (Why is that?)
- On the Piano Movers' problem: IV. Various decomposable two-dimensional motion-planning problems
- Coordinated motion planning for two independent robots
- Solving the two-dimensional findpath problem using a line-triangle representation of the robot
Cited In (36)
- On lazy randomized incremental construction
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
- Combinatorial complexity of signed discs
- The number of edges of many faces in a line segment arrangement
- The Set of Admissible Positions for a Two‐DOF Linkage in the Presence of Obstacles
- Storing line segments in partition trees
- Combinatorial complexity of signed discs
- Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
- Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
- Coordinated motion planning for two independent robots
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Computing a single cell in the overlay of two simple polygons
- Combinatorial complexity of translating a box in polyhedral 3-space
- A new algorithm for shortest paths among obstacles in the plane
- GUARDING A POLYGON FROM TWO NEARLY-OPPOSITE DIRECTIONS
- The complexity and construction of many faces in arrangements of lines and of segments
- On the complexity of a single cell in certain arrangements of surfaces related to motion planning
- Constrained Minkowski sums: A geometric framework for solving interval problems in computational biology efficiently
- Castles in the air revisited
- Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
- Two optimal path planning problems for a moving object in the case of degeneration of necessary extremum conditions
- An optimal algorithm for the boundary of a cell in a union of rays
- Minimum Cell Connection in Line Segment Arrangements
- The upper envelope of piecewise linear functions: Algorithms and applications
- Preprocessing chains for fast dihedral rotations is hard or even impossible.
- Excess in arrangements of segments
- Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
- The common exterior of convex polygons in the plane
- Robot motion planning and the single cell problem in arrangements
- Title not available (Why is that?)
- Almost tight upper bounds for the single cell and zone problems in the three dimensions
- Polyhedral Assembly Partitioning Using Maximally Covered Cells in Arrangements of Convex Polytopes
- Title not available (Why is that?)
- A convex polygon among polygonal obstacle: Placement and high-clearance motion
- On arrangements of Jordan arcs with three intersections per pair
This page was built for publication: On the general motion-planning problem with two degrees of freedom
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1262130)
