A convex polygon among polygonal obstacle: Placement and high-clearance motion
Given a convex polygon \(P\) and an environment consisting of polygonal obstacles, we find the placement for the largest similar copy of \(P\) that does not intersect any of the obstacles. Allowing translation, rotation, and change-of-size, our method combines a new notion of Delaunay triangulation for points and edges with the well-known functions based on Davenport-Schinzel sequences, producing an almost quadratic algorithm for the problem. Namely, if \(P\) is a convex \(k\)-gon and if \(Q\) has \(n\) corners and edges then we can find the placement of the largest similar copy of \(P\) in the environment \(Q\) in time \(O(k^ 4n\lambda_ 3(n)\log n)\), where \(\lambda_ 3\) is one of the almost-linear functions related to Davenport-Schinzel sequences. Based on our complexity analysis of the placement problem, we develop a high-clearance motion planning technique for a convex polygonal object moving among polygonal obstacles in the plane, allowing both rotation and translation (general motion). Given a \(k\)-sided convex polygonal object \(P\), a set of polygonal obstacles with \(n\) corners and edges, and given initial and final positions for \(P\), the time needed to determine a high-clearance, obstacle-avoiding path for \(P\) is \(O(k^ 4n\lambda_ 3(n)\log n)\).
- Motion planning for a convex polygon in a polygonal environment
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
- A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment
- An efficient algorithm for computing high-quality paths amid polygonal obstacles
- Largest placement of one convex polygon inside another
- A sweepline algorithm for Voronoi diagrams
- A “retraction” method for planning the motion of a disc
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
- An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
- Constrained Delaunay triangulations
- Generalized Delaunay triangulation for planar graphs
- Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
- Generalized voronoi diagrams for moving a ladder. I: Topological analysis
- scientific article; zbMATH DE number 3911704 (Why is no real title available?)
- scientific article; zbMATH DE number 4051003 (Why is no real title available?)
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On the general motion-planning problem with two degrees of freedom
- On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Some dynamic computational geometry problems
- Constrained Minkowski sums: A geometric framework for solving interval problems in computational biology efficiently
- Motion planning for a convex polygon in a polygonal environment
- Extremal polygon containment problems
- Combinatorial complexity of translating a box in polyhedral 3-space
- A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment
- Mathematical modeling of interactions of primary geometric 3D objects
- Empty squares in arbitrary orientation among points
- Computing the maximum overlap of two convex polygons under translations
- Matching convex polygons and polyhedra, allowing for occlusion
- Near-quadratic bounds for the \(L_ 1\) Voronoi diagram of moving points
- Largest similar copies of convex polygons in polygonal domains
- Convex polygon containment: improving quadratic to near linear time
- Maximum-area and maximum-perimeter rectangles in polygons
This page was built for publication: A convex polygon among polygonal obstacle: Placement and high-clearance motion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685605)
