Calculation of partially convex hulls and approximations for finite planar sets (Q1571224)

The paper is devoted to the computational aspects of partial convexity in the space \(\mathbb R^2\). Certain classes of partial convexity and the corresponding hulls are considered. For a finite set of points, efficient algorithms for calculating these hulls are developed. An algorithm is proposed for calculating the densest partially convex outer approximation for a finite set of points with a constraint on the mesure of complexity of its shape. This approximation is calculated by the reduction to a certain discrete extremal problem on a graph.