# Finding C-convex holes in a planar point set

I am looking for an efficient algorithm to find convex holes in a given point set. The problem is

Given $$n$$ points in the Euclidan plane, and a constant $$c$$, determine how many empty convex polygons $$P_1, \dots, P_k$$ there are, such that for each $$i = 1,\dots,k$$, $$P_i$$ has vertices from the given point set.

Although there are some papers that considers finding possibly non convex holes [1] [2] [3], and some others that show existence of such holes [4] [5], I could not find a paper that describes an algorithm to find them.

Obviously, a naive algorithm that runs in $$\mathcal{O}(n^c)$$ comes to mind, where each $$c$$-subset is traversed. However, I would like to know whether there exists a more efficient algorithm.

• What's an empty polygon? Also, the problem statement does not depend on $c$, so something seems missing. – D.W. Feb 14 at 9:20