An efficient algorithm for minimum zone flatness based on the computation of the largest inscribed ball in a symmetric polyhedron

This paper presents an algorithm for the minimum zone flatness tolerance of a finite point set, which is defined to be the minimum Euclidean distance between two parallel planes that sandwich the point set. The algorithm is based on the observation that the flatness tolerance is equal to the radius of the largest inscribed ball in the convex hull of the Minkowski difference of the point set and itself, which is a symmetric polyhedron with respect to the origin. Then, an iterative procedure is developed to adaptively grow another symmetric polyhedron inside the convex hull of the Minkowski difference such that the radius of its inscribed ball monotonically increases and converges to the flatness tolerance. The algorithm is guaranteed to compute the globally minimum solution within finite iterations. Moreover, there is no need to compute the Minkowski difference or the convex hull of the point set, so the proposed algorithm is very fast and takes only several milliseconds for hundreds of thousands of points on a normal computer, such as a desktop computer with an Intel Xeon 3.70 GHz CPU and 16GB RAM used in this work.