Item Details

Print View

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
2012-10-29
Published
University of Virginia, Department of Computer Science, 1987
Published Date
1987
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online