Finding Farthest Neighbors in a Convex Polygon and Related Problems
Abstract
Aggarwal et al. showed how to compute in O(n) 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; 3)An 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1989
- Accession Number
- ADA210727
Entities
People
- Dina Kravets
Organizations
- Massachusetts Institute of Technology