Finding Extremal Polygons
James E. Boyce, David Dobkin, Robert L. Scot Drysdale, Leo J. Guibas · SIAM Journal on Computing · 1985
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(kn\lg n + n\lg ^2 n)$. For the special case $k = 3$ we give $O(n\lg n)$ algorithms for these problems. Several related issues are discussed.