Hausdorff approximation of convex polygons (Q2573338)

The authors develop algorithms for the approximation of convex polygons with \(n\) vertices by convex polygons with fewer \((k)\) vertices. The distance function used to measure the quality of the approximation is the Hausdorff metric. For this purpose, authors consider two types of problems: min-\(\sharp\), where the goal is to minimize the number of vertices of the output polygon, for a given distance \(\epsilon\), and min-\(\epsilon\), where the goal is to minimize the error, for a given maximum number of vertices. For min-\(\sharp\) problems, the presented algorithms are guaranteed to be within one vertex of the optimal, and run in \({\mathcal O}(nlogn)\) and \({\mathcal O}(n)\) time, for inner and outer approximations, respectively. For min-\(\epsilon\) problems, the error achieved is within an arbitrary factor \(a>1\) from the best possible one, and the inner and outer approximation algorithms run in \({\mathcal O}(f(a,P)\cdot nlogn)\) and \({\mathcal O}(f(a,P)\cdot n)\) time, respectively. The factor \(f(a,P)\) that has a reciprocal logarithmic growth as \(a\) decreases to \(1\). This factor depends on the shape of the approximated polygon \(P\). Upper bounds for \(f(a,P)\) are also provided.