2
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.