Item Details

Interdistance Selection by Parametric Search

Salowe, Jeffrey
Format
Report
Author
Salowe, Jeffrey
Abstract
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
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1987
Published Date
1987
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online