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.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.