We provide an efficient reduction from the problem of querying approximate multiplicatively weighted farthest neighbors in a metric space to the unweighted problem. Combining our techniques with core-sets for approximate unweighted farthest neighbors, we show how to find approximate farthest neighbors that are farther than a factor (1-e) of optimal in time O(logn) per query in D-dimensional Euclidean space for any constants D and e. As an application, we find an O(nlog n) expected time algorithm for choosing the center of a star topology network connecting a given set of points, so as to approximately minimize the maximum dilation between any pair of points.
['John Augustine', 'David Eppstein', 'Kevin A. Wortman']
Approximate weighted farthest neighbors and minimum dilation stars