quadrangulations

A quadrangulation is a geometric partitioning of a polygon into quadrilaterals. More specifically, it is a decomposition of a polygon into a set of non-overlapping quadrilaterals whose union is the original polygon. The edges of these quadrilaterals are either edges of the original polygon or diagonals connecting vertices of the polygon.

Quadrangulations are a type of mesh generation technique used in various fields, including computer graphics, computational geometry, and finite element analysis. They are particularly useful for discretizing surfaces for simulation and rendering purposes. The quality of a quadrangulation, often measured by the shape and size of its constituent quadrilaterals, can significantly impact the accuracy and efficiency of numerical methods.

There are different types of quadrangulations, such as Delaunay quadrangulations, which aim to produce quadrilaterals that are as "regular" as possible, avoiding thin or elongated shapes. Generating high-quality quadrangulations, especially for complex geometries, is a challenging problem in computational geometry. Algorithms exist to construct quadrangulations, often starting with an initial triangulation and then refining it by merging triangles into quadrilaterals. The study of quadrangulations is an active area of research, with ongoing efforts to develop more efficient and robust algorithms for their generation and manipulation.