Computation of the tangent graph of polygonal obstacles by moving-line processing

Abstract

The tangent graph is a powerful graphic data structure for the path-planning of a mobile robot among obstacles because it has fewer edges than the widely used visibility graph. This paper proposes an efficient algorithm for computing the tangent graph of a set of polygonal obstacles, The algorithm at first detects common tangents of obstacle boundaries by moving-line processing that cooperatively moves a straight segment on the boundaries, and then checks for intersections among detected tangents and the obstacles both by a sequential approach and a sweep-line technique. It is proved that the moving-line processing takes O(MN) and O([M+R]N) computation time in the best and worst cases, respectively, where N expresses the number of obstacle vertices, and M denotes the number of convex segment chains of the obstacle boundaries, and R is a parameter representing the complexity of the boundaries.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>