L-infinity interdistance selection by parametric search
type: Item
instance of: scholarly article
title: L-infinity interdistance selection by parametric search
zbMATH Open document ID: 0664.68063
DOI: 10.1016/0020-0190(89)90166-X
author: Jeffrey S. Salowe
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: The selection problem asks for the kth largest or smallest element in a set S. In general, selection takes linear time, but if the set is constrained so that some relations between elements are known, sublinear- time selection is sometimes possible. We present an algorithm that selects the kth largest or smallest element from a Cartesian sum in O(n log n) time and extend this result to select \(L_{\infty}\)- interdistances in \({\mathbb{R}}^ d\) in O(d n \(log^{d-1} n)\) time. The algorithm is based on a general technique of Megiddo and improved by Cole, and it is the first algorithm for a multidimensional interdistance selection problem with an O(n \(log^{O(1)}n)\) running time.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4087036
zbMATH Keywords: computational geometry
zbMATH Keywords: geometric selection
zbMATH Keywords: multidimensional interdistance selection
MaRDI profile type: Publication
cites work: Sorting in \(c \log n\) parallel steps
cites work: Q4140384
cites work: Time bounds for selection
cites work: Slowing down sorting networks to obtain faster sorting algorithms
cites work: Q3795242
cites work: The complexity of selection and ranking in X+Y and matrices with sorted columns
cites work: A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort
cites work: Combinatorial Optimization with Rational Objective Functions
cites work: Applying Parallel Computation Algorithms in the Design of Serial Algorithms
cites work: Q3992847
cites work: Q4028890
cites work: Q4176809
cites work: Parallelism in Comparison Problems
cites work: New Data Structures for Orthogonal Range Queries
description: scientific article; zbMATH DE number 4087036