A convex polygon among polygonal obstacle: Placement and high-clearance motion (Q685605)

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)\).