A combinatorial property on angular orders of plane point sets

We study the following combinatorial property of point sets in the plane: For a set S of n   points in general position and a point p∈Sp∈S consider the points of S−pS−p in their angular order around p. This gives a star-shaped polygon (or a polygonal path) with p   in its kernel. Define c(p)c(p) as the number of convex angles in this star-shaped polygon around p  , and c(S)c(S) as the sum of all c(p)c(p), for p∈Sp∈S. We show that for every point set S  , c(S)c(S) is always at least 12n32−O(n). This bound is shown to be almost tight. Consequently, every set of n   points admits a star-shaped polygonization with at least n2−O(1) convex angles.

► We study a combinatorial property of point sets related to counting empty triangles. ► A lower bound on the number of convex angles in angular orders of point sets is shown. ► This bound is almost tight. ► We present a bound on the number of convex angles in star-shaped polygonizations.