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.

  • 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

Your Answer

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

Browse other questions tagged or ask your own question.