On Spanning Trees with Low Crossing Number

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$).

Weighted Closest Pairs

Michael Formann Institut für Informatik Freie Universität Berlin Report B 92-04 February 92