DefinePK

Abstract

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.