Can a fourth point(vertex) be on the circumference of a circumcircle formed by 3 points in Delaunay triangulation?

104 Views Asked by At

I understand that in Delaunay triangulation that no points should be placed inside any of the circumcircles , but is a fourth point allowed to be on the circumference of the circle other than the 3 original points which formed the circle. If it is not allowed then how can we perform Delaunay triangulation on the four vertices of a square because the fourth vertex always falls on the circumference of the circumcircle.

1

There are 1 best solutions below

0
On BEST ANSWER

The Delaunay diagram is the dual of the Voronoi diagram.

The Delaunay diagram is a triangulation iff there are no four cocircular points.

When there are four or more cocircular points, the corresponding Delaunay face can be triangulated arbitrarily.