Optimal slope selection via cuttings

We give an optimal deterministic O( n log n)-time algorithm for slope selection. The algorithm borrows from the optimal solution given in (Cole et al., 1989) but avoids the complicated machinery of the AKS sorting network and parametric searching. This is achieved by redesigning and refining the O(...

Full description

Saved in:
Bibliographic Details
Published in:Computational geometry : theory and applications 1998-04, Vol.10 (1), p.23-29
Main Authors: Brönnimann, Hervé, Chazelle, Bernard
Format: Article
Language:English
Subjects:
Arrangements
Deterministic optimal algorithm
Sorting
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We give an optimal deterministic O( n log n)-time algorithm for slope selection. The algorithm borrows from the optimal solution given in (Cole et al., 1989) but avoids the complicated machinery of the AKS sorting network and parametric searching. This is achieved by redesigning and refining the O( n log 2 n)-time algorithm of Chazelle et al. (1993) with the help of additional approximation tools.
ISSN:0925-7721
DOI:10.1016/S0925-7721(97)00025-4