Weighted Closest Pairs
Michael Formann
Institut für Informatik
Freie Universität Berlin
Report B 92-04
February 92
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-92-04.ps.gz
In this paper we study the following {\it weighted closest pair problem}: Given a set of planar objects with centerpoints, determine the {\it maximal scaling factor} $\delta_{max}$, such that the objects scaled by $\delta_{max}$ are pairwise disjoint. We describe a method to compute the maximal scaling factor in optimal $\bigO(n\log n)$ time for a
wide class of objects, including disks
generated by $L_p$-norms ($1 \leq p \leq \infty$).