Skip to main content
Download PDF
- Main
New algorithms for minimum area k-gons
Abstract
Given a set P of n points in the plane, we wish to find a set Q C P of k points for which the convex hull conv(Q) has the minimum area. We solve this, and the related problem of finding a minimum area convex k-gon, in time O(n^2 log n) and space O(n log n) for fixed k, almost matching known bounds for the minimum area triangle problem. Our algorithm is based on finding a certain number of nearest vertical neighbors to each line segment determined by two input points. We use a classical result of Ramsey theory to prove that these nearest neighbors suffice to determine the minimum convex k-gon.
Main Content
For improved accessibility of PDF content, download the file to your device.
Enter the password to open this PDF file:
File name:
-
File size:
-
Title:
-
Author:
-
Subject:
-
Keywords:
-
Creation Date:
-
Modification Date:
-
Creator:
-
PDF Producer:
-
PDF Version:
-
Page Count:
-
Page Size:
-
Fast Web View:
-
Preparing document for printing…
0%