An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space (Q1263972)

Let B be a convex polygon of k vertices and k edges. B is free to move (translate and rotate) in an open two-dimensional area bounded by a collection of polygonal obstacles having altogether n corners. The problem is to plan a continuous obstacle-avoiding motion of B from a given initial place to a given final place. The authors presented an algorithm with time-complexity O(kn \(\lambda_ 6(kn)\log kn)\), where \(\lambda_ s(q)\) is an almost linear function of q yielding the maximal number of connected portion of q continuous functions which compose the graph of their lower envelope, under the condition tht each pair of these functions intersect in at most s points. This is an elegant result.