DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# 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

# 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.

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#