Finding Farthest Neighbors in a Convex Polygon and Related Problems

摘要

Aggarwal et al. showed how to compute in O(n) time one farthest vertex for every vertex of a convex n-gon. The thesis extends the results of Aggarwal et al. by developing the following algorithm: 1) An optimal algorithm to find all farthest vertices 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 a set of numbers given lower bounds on the ranks. Keywords: Computational geometry, Monotone matrices, Sorting. (KR)