An Upper Bound for Min-Max Angle of Polygons

Abstract

‎Let $S$ be a set of $n$ points in the plane‎, ‎$\nabla(S)$ the set of all simple polygons crossing $S$‎, ‎$\gamma_P$ the maximum angle of polygon $P \in \nabla(S)$ and $\theta =min_{P\in\nabla(S)} \gamma_P$‎. ‎In this paper‎, ‎we prove that $\theta\leq 2\pi-\frac{2\pi}{r.m}$ 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 $\theta$ and prove that this is tight for $r=1$‎.

Keywords

• min-max angle‎
• ‎upper bound‎
• ‎sweep arc‎
• ‎simple polygonization‎
• ‎computational geometry‎