Approximate Weighted Farthest Neighbors and Minimum Dilation Stars
<|reference_start|>Approximate Weighted Farthest Neighbors and Minimum Dilation Stars: 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 (1+epsilon)-approximate farthest neighbors in time O(log n) per query in D-dimensional Euclidean space for any constants D and epsilon. As an application, we find an O(n log 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.<|reference_end|>
@article{augustine2006approximate,
    title={Approximate Weighted Farthest Neighbors and Minimum Dilation Stars},
    author={John Augustine and David Eppstein and Kevin A. Wortman},
    journal={arXiv preprint arXiv:cs/0602029},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0602029},
    primaryClass={cs.CG cs.DS}
}