Computation of the medial axis of planar domains based on saddle point programming

This paper presents a saddle point programming approach to compute the medial axis (MA). After exploring the saddle point properties of the medial axis transform (MAT), the mathematical programming method is employed to establish the saddle point programming model of the MAT. By using the optimal conditions, i.e., the number and distribution of the tangent points between the boundary and medial axis disk, the one- and two-dimensional saddle point algorithms are developed. In order to determine the branch point, it is better to consider its generating mechanism. Here, we identify the branch point according to the sudden changes of the solutions to the one-dimensional saddle point algorithm. Hence, all the regular and irregular points of MA can be computed by a general algorithm, and it is proved to be efficient and accurate by the numerical examples.

► We study the saddle point properties of the MAT. ► The medial axis points are solved by the saddle point programming models. ► The branch point is identified by the sudden changes in the tracing process. ► The global searching process for the minimum distance has been modified.