Selecting the Kth Largest-Area Convex PolygonReport
Given a set P of n points in the Euclidean plane, consider the convex polygons determined by subsets of P. We show that the problem of selecting the kth largest-area convex polygon is NP- hard by a reduction from the problem of finding the kth largest m-tuple  determined by m sets X 1,X2, . . . ,X,,,. The problem of finding the convex polygon with kth largest area was introduced by Chazelle  as an example of a multidimensional selection problem for which the time complexity of selecting the median seems inherently difficult.
Note: Abstract extracted from PDF file via OCR
All rights reserved (no additional license for public reuse)
Salowe, Jeffrey. "Selecting the Kth Largest-Area Convex Polygon." University of Virginia Dept. of Computer Science Tech Report (1988).
University of Virginia, Department of Computer Science