Generalized Delaunay triangulation for planar graphs (Q1078807)

The Delaunay triangulation of a planar straight line graph has the property that the circumcircle of any triangle does not contain any other vertex in its interior. The authors introduce a generalized Delaunay triangulation such that this circumcircle contains no vertices which are visible from the three vertices of the triangle. It is shown that there exists a unique generalized Delaunay triangulation, and that the minimum angle of the triangles in the triangulation is maximum among all possible triangulations of the graph. Finally, an \(0(n^ 2)\) algorithm for the construction is presented where n is the number of vertices.