Given a finite set S of points in the plane in general position, a polygon of k corners chosen from S is called a k-gon of S, and a k-gon is called a k-hole if it contains no other points of S in its interior. In this talk, we are interested in the problem of counting k-gons or k-holes of S for a given set S and an integer k. Considering the computational complexity of these counting problems, this talk covers known combinatorial results on k-gons and k-holes, algorithms that count them, lower bounds, and open research problems.
