Interdistance Selection by Parametric SearchReport
The selection problem asks for the k"' largest or smallest element in a set S. In general, selection takes linear time, but if the set is constrained so that sotne relations between elements are known, sublinear time selection is sometimes possible. Chazelle  described one technique for selection when the set is constrained by geometry. This paper demonstrates a new technique for geometric selection problems based on the idea of parametric search [6, 14, 16] and applies it to show that given n points in SR‘, the k"‘ largest L._, interdistance can be selected in 0(d n log‘ n) time. This is the first selection algorithm for multidimensional interdistances to run in 0 (:1 logo") n) time. KEYWORDS Selection, interdistance, Computational Geometry.
Note: Abstract extracted from PDF file via OCR
All rights reserved (no additional license for public reuse)
Salowe, Jeffrey. "Interdistance Selection by Parametric Search." University of Virginia Dept. of Computer Science Tech Report (1987).
University of Virginia, Department of Computer Science