David Eppstein - Publications

Publications with John Augustine

• Approximate weighted farthest neighbors and minimum dilation stars.
  J. Augustine, D. Eppstein, and K. Wortman.
  arXiv:cs.CG/0602029.
  Proc. 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam.
  Springer, Lecture Notes in Comp. Sci. 6196, 2010, pp. 90–99.
  Discrete Mathematics, Algorithms and Applications 2 (4): 553–565, 2010.

  The problem is to quickly find, in a set of sites with weights, the site maximizing the product of its weight with its distance from the query point. Our solution combines known results on core-sets with a reduction from the weighted to the unweighted problem that works in any metric space. This leads to fast approximation algorithms for the constrained minimum dilation star problem in any fixed dimension.