Finding Farthest Neighbors in a Convex Polygon and Related Problems
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Pagination or Media Count:
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.
- Theoretical Mathematics