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(nk-2) algorithm
for this problem, improving over the trivial O(nk)
algorithm.
In the second paper, a refinement of the technique improves
the complexity to O(nfloor(k/2)).
This time bound has been subsequently improved
to O(k n3) in the third paper.
Last update: August 30, 2004.