An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space (Q1263972): Difference between revisions
From MaRDI portal
Revision as of 12:02, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space |
scientific article |
Statements
An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space (English)
0 references
1990
0 references
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.
0 references
polygon motion
0 references
time-complexity
0 references
computational geometry
0 references
polygonal obstacles
0 references
0 references
0 references
0 references
0 references
0 references
0 references