Selecting the Kth Largest-Area Convex Polygon

Author:Salowe, Jeffrey, Department of Computer ScienceUniversity of Virginia

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 [3] determined by m sets X 1,X2, . . . ,X,,,. The problem of finding the convex polygon with kth largest area was introduced by Chazelle [1] 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)
Source Citation:

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
Published Date: