Finding extremal polygons

Abstract

Given n points in the plane, we present algorithms for finding maximum perimeter or area convex k-gons with vertices k of the given n points. Our algorithms work in linear space and time O(knlg n + n lg 2n). For the special case k = 3 we give O (nlgn) algorithms for these problems. Several related issues are discussed.