Finding C-convex holes in a planar point set

Question

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.

Answer 1

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).