Item Details

Print View

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
2012-10-29
Published
University of Virginia, Department of Computer Science, 1988
Published Date
1988
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online