An Upper Bound for Min-Max Angle of Polygons

Let S be a set of n points in the plane, ∇(S) the set of all simple polygons crossing S, γP the maximum angle of polygon P ∈ ∇(S) and θ = minP∈∇(S)γP . In this paper, we prove that θ ≤ 2π − 2π where m and r are the number of edges and inner points of the convex hull of S, respectively. We also propose an algorithm to construct a polygon with the upper bound on its angles. Constructing a simple polygon with the angular constraint on a given set of points in the plane can be used for path planning in robotics. Moreover, we improve our upper bound on θ and prove that this is tight for r = 1.