Item Details

Selecting the Kth Largest-Area Convex Polygon

Salowe, Jeffrey
Format
Report
Author
Salowe, Jeffrey
Abstract
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
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1988
Published Date
1988
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online