Interdistance Selection by Parametric Search

Author:Salowe, Jeffrey, Department of Computer ScienceUniversity of Virginia

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 [5] 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)
Source Citation:

Salowe, Jeffrey. "Interdistance Selection by Parametric Search." University of Virginia Dept. of Computer Science Tech Report (1987).

University of Virginia, Department of Computer Science
Published Date: