Accession Number:

ADA210727

Title:

Finding Farthest Neighbors in a Convex Polygon and Related Problems

Descriptive Note:

Master's thesis

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

• Kravets, Dina

Report Date:

1989-01-01

Pagination or Media Count:

31.0

Abstract:

Aggarwal et al. showed how to compute in On time one farthest vertex for every vertex of a convex n-gon. Thesis extends the results of Aggarwal et. al. by developing the following algorithms 1 An optimal algorithms to find all farthest vetices for every vertex of a convex polygon 2 An O knlogk time algorithm to find k farthest vertices for every vertex of a convex n-gon 3An O sg n algorithm to sort the distances of all the vertices of a convex n-gon with respect to each vertex of the convex n-gon and 4 a worst- case optimal algorithm to sort of set of a numbers given lower bounds on the ranks.

Descriptors:

• *POLYGONS
• OPTIMIZATION
• COMPUTATIONS
• CONVEX BODIES
• GEOMETRY
• SORTING
• ALGORITHMS
• TIME

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE