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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)
other papers about this subject
Last update: August 30, 2004.