Efficient enumeration of at most k-out polygons

Let S be a set of n points in the Euclidean plane and general position i.e., no three points are collinear. An at most k-out polygon of S is a simple polygon such that each vertex is a point in S and there are at most k points outside the polygon. In this paper, we consider the problem of enumerating all the at most k-out polygon of S. We propose a new enumeration algorithm for the at most k-out polygons of a point set. Our algorithm enumerates all the at most k-out polygons in O(n² logn) delay, while the running time of an existing algorithm is O(n³ logn) delay.