Analysis of the Computational Cost of PolyFront: an Algorithm for Planar Triangulation
Abstract - 59


Mesh generation
Polygon offsetting
Computational cost
Two-dimensional delaunay triangulation

How to Cite

Egidi, N., Giacomini, J., Misici, L., Perticarini, A., & Piergallini, R. (2023). Analysis of the Computational Cost of PolyFront: an Algorithm for Planar Triangulation. Journal of Advances in Applied & Computational Mathematics, 10, 50–64.


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.


Wang Q, Ye J, Wu H, Gao B, Shepherd P. A triangular grid generation and optimization framework for the design of free-form gridshells. Comput Aid Des. 2019; 113: 96–113.

Liu F, Feng R. Automatic triangular grid generation on a free-form surface using a particle self-organizing system. Eng Comput. 2020; 36: 377–89.

Liu F, Feng R, Tsavdaridis KD. A novel progressive grid generation method for free-form grid structure design and case studies. J Build Eng. 2021; 34: 101866.

Liseikin V. Grid generation methods. vol. 1, Springer; 1999, p. 1–29.

Thompson JF. Handbook of grid generation. 1st Edition. Boca Raton: CRC Press; 1999.

George P-L, Houman Borouchaki. Delaunay triangulation and meshing. vol. 1. Paris: 1998.

Parthasarathy VN, Graichen CM, Hathaway AF. A comparison of tetrahedron quality measures. Finite Elem Anal Des. 1994; 15: 255–61.

Mandad M, Campen M. Guaranteed-quality higher-order triangular meshing of 2D domains. ACM Trans Graph. 2021; 40: 1–14.

Egidi N, Misici L, Piergallini R. PolyFront: an algorithm for fast generation of the high-quality triangular mesh. Eng Comput. 2011; 27: 357–72.

Blacker TD, Stephenson MB. Paving: A new approach to automated quadrilateral mesh generation. Int J Numer Methods Eng. 1991; 32: 811–47.

van Rens BJE, Brokken D, Brekelmans WAM, Baaijens FPT. A two-dimensional paving mesh generator for triangles with controllable aspect ratio and quadrilaterals with high quality. Eng Comput. 1998; 14: 248–59.

George JA. Computer implementation of the finite element method. Stanford University; 1971.

Lo SH. A new mesh generation scheme for arbitrary planar domains. Int J Numer Methods Eng. 1985; 21: 1403–26.

Löhner R. Progress in grid generation via the advancing front technique. Eng Comput. 1996; 12: 186–210.

Peraire J, Vahdati M, Morgan K, Zienkiewicz OC. Adaptive remeshing for compressible flow computations. J Comput Phys. 1987; 72: 449–66.

Egidi N, Misici L, Pennesi R. An algorithm for planar triangulations. A graphical user interface. Proceedings of MASCOT03-3rd Meeting on Applied Scientific Computing and Tools, Grid Generation, Approximation and Visualization, Roma: IMACS Series in Computational and Applied Mathematics; 2004, p. 71–80.

Watson DF. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput J. 1981; 24: 167–72.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2023 Nadaniela Egidi, Josephin Giacomini, Luciano Misici, Alessia Perticarini, Riccardo Piergallini