# 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 exactly $$c$$ 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

In "Counting Convex Polygons in Planar Point Sets" (link) Mitchell et al. show an algorithm which can do this in time $$O(cn^3)$$.
Note however that if you need to report those polygons then you can't do better than $$O(n^c)$$ as there might be $$\Omega(n^c)$$ such polygons to begin with (consider for example $$n$$ points in convex position).