Analysis of the Computational Cost of PolyFront: an Algorithm for Planar Triangulation - Egidi, Nadaniela; Giacomini, Josephin; Misici, Luciano; Perticarini, Alessia; Piergallini, Riccardo (Journal of Advances in Applied & Computational Mathematics, 2023)
The triangulation of planar domains is a relevant and largely studied problem in many applied sciences. This paper analyzes the computational time of a triangulation algorithm for plane domains with holes, introduced in a previous paper. This algorithm is based on the normal offsetting technique starting from a polygonal approximation of the domain boundary. It is shown that the computational time is linear with respect to the number of vertices of the triangulation. Experimental results confirm the theoretical upper bound obtained for the computational time.