On shortest path problem in a polygon and its applications

摘要

Geometric properties of the shortest path in a polygon are investigated and described. The properties are described by convex hulls and by relative support lines. The most efficient algorithm for the shortest path problem solution in a polygon based on the pseudomonotone polygon partition is described. It is shown that the visibility polygon partition of a polygon has a direct impact on the shortest path motion planning of a robot with an active sensor.