Optimal slope selection via cuttings

Hervé Brönnimann; Bernard Chazelle

doi:10.1016/S0925-7721(97)00025-4

Optimal slope selection via cuttings

Hervé Brönnimann, Bernard Chazelle

Research output: Contribution to journal › Article › peer-review

34 Scopus citations

Abstract

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² n)-time algorithm of Chazelle et al. (1993) with the help of additional approximation tools.

Original language	English (US)
Pages (from-to)	23-29
Number of pages	7
Journal	Computational Geometry: Theory and Applications
Volume	10
Issue number	1
DOIs	https://doi.org/10.1016/S0925-7721(97)00025-4
State	Published - Apr 1998
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Keywords

Arrangements
Deterministic optimal algorithm
Sorting

Access to Document

10.1016/S0925-7721(97)00025-4

Cite this

@article{4722e0bb0eb74eb185d4ceaf060934f5,

title = "Optimal slope selection via cuttings",

abstract = "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 log2 n)-time algorithm of Chazelle et al. (1993) with the help of additional approximation tools.",

keywords = "Arrangements, Deterministic optimal algorithm, Sorting",

author = "Herv{\'e} Br{\"o}nnimann and Bernard Chazelle",

year = "1998",

month = apr,

doi = "10.1016/S0925-7721(97)00025-4",

language = "English (US)",

volume = "10",

pages = "23--29",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Optimal slope selection via cuttings

AU - Brönnimann, Hervé

AU - Chazelle, Bernard

PY - 1998/4

Y1 - 1998/4

N2 - 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 log2 n)-time algorithm of Chazelle et al. (1993) with the help of additional approximation tools.

AB - 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 log2 n)-time algorithm of Chazelle et al. (1993) with the help of additional approximation tools.

KW - Arrangements

KW - Deterministic optimal algorithm

KW - Sorting

UR - http://www.scopus.com/inward/record.url?scp=0040039965&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040039965&partnerID=8YFLogxK

U2 - 10.1016/S0925-7721(97)00025-4

DO - 10.1016/S0925-7721(97)00025-4

M3 - Article

AN - SCOPUS:0040039965

SN - 0925-7721

VL - 10

SP - 23

EP - 29

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 1

ER -

Optimal slope selection via cuttings

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this