Convex hole

For a finite point set in the plane, a convex polygon whose vertices of a polygon belong to the set and whose interior contains no point of the set. The convention must specify whether additional points on the boundary are allowed. A fan triangulation reduces emptiness to tests on constituent triangles, together with checks that internal diagonals contain no forbidden points.