## 1. Gerhard Woeginger, Günter Rote, Binhai Zhu, and Zhengyan
Wang :

# Counting *k*-subsets and convex *k*-gons in the plane

*Information Processing Letters 38 (1991), 149-151,
(Zbl 737.68084,
MR #92i:68183).*
## 2. Günter Rote and Gerhard Woeginger:

# Counting convex *k*-gons in planar point sets

*Information Processing Letters 41 (1992), 191-194, (Zbl 751.68077,
MR #93c:68108).*
## 3. Joseph S. B. Mitchell, Günter Rote, Gopalakrishnan
Sundaram, and
Gerhard Woeginger:

# Counting convex polygons in planar point sets

*Information Processing Letters 56 (1995), 45-49, (Zbl 875.68899).
*
### Abstract

Given *n* points in the plane and an integer *k*,
between 4 and *n*, we want to compute the overall number of
convex *k*-gons whose corners belong to the given point set.
The first paper
gives an *O*(*n*^{k-2}) algorithm
for this problem, improving over the trivial *O*(*n*^{k})
algorithm.
In the second paper, a refinement of the technique improves
the complexity to *O*(*n*^{floor(k/2)}).
This time bound has been subsequently improved
to *O*(*k n*^{3}) in the third paper.

Last update: August 30, 2004.