Preeti Malakar, Thomas George, et al.
SC 2012
Aggarwal et al. [A. Aggarwal, M.M. Klawe, S. Moran, P. Shor and R. Wilber, Geometric applications of a matrix-searching algorithm, Algorithmica 2 (1987) 209-233] showed how to compute in O(n) time one farthest neighbor for every vertex of a convex n-gon. In this note we extend this result to obtain a linear time algorithm for finding all farthest neighbors for every vertex of a convex polygon. Our algorithm yields a linear time solution to the symmetric all-farthest neighbors problem for simple polygons, thereby settling an open question raised by Toussaint in 1983 [G.T. Toussaint, The symmetric all-farthest neighbor problem, Comp. Math. Appl. 9 (6) (1983) 747-753.]. © 1989.
Preeti Malakar, Thomas George, et al.
SC 2012
Indranil R. Bardhan, Sugato Bagchi, et al.
JMIS
Minkyong Kim, Zhen Liu, et al.
INFOCOM 2008
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science