Counting convex \(k\)-gons in planar point sets (Q1190511)

Given \(n\) points in the plane and an integer \(k\), \(4\leq k\leq n\), we want to compute the overall number of convex \(k\)-gons whose corners belong to the given point set. \textit{G. Rote}, \textit{Z. Wang}, \textit{G. Woeginger} and \textit{B. Zhu} [Counting \(k\)-subsets and convex \(k\)-gons in the plane, Inform. Process. Lett. 38, 149-151 (1991)] gave an \(O(n^{k- 2})\) algorithm for this problem, improving over the trivial \(O(n^ k)\) algorithm. We refine their methods and reach a time complexity of \(O(n^{\lceil k/2\rceil})\).