Derandomizing an output-sensitive convex hull algorithm in three dimensions

Bernard Chazelle; Jiří Matoušek

doi:10.1016/0925-7721(94)00018-Q

Derandomizing an output-sensitive convex hull algorithm in three dimensions

Bernard Chazelle, Jiří Matoušek

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

24 Scopus citations

Abstract

We consider the computation of the convex hull of a given n-point set in three-dimensional Euclidean space in an output-sensitive manner. Clarkson and Shor proposed an optimal randomized algorithm for this problem, with an expected running time O(n log h), where h denotes the number of points on the surface of the convex hull. In this note we point out that the algorithm can be made deterministic by using recently developed techniques, thus obtaining an optimal deterministic algorithm.

Original language	English (US)
Pages (from-to)	27-32
Number of pages	6
Journal	Computational Geometry: Theory and Applications
Volume	5
Issue number	1
DOIs	https://doi.org/10.1016/0925-7721(94)00018-Q
State	Published - Mar 1995
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

Computational complexity
Computational geometry
Convex hull
Randomized algorithm

Access to Document

10.1016/0925-7721(94)00018-Q

Cite this

@article{4fd6c13ca578420190715ae1beac43ef,

title = "Derandomizing an output-sensitive convex hull algorithm in three dimensions",

abstract = "We consider the computation of the convex hull of a given n-point set in three-dimensional Euclidean space in an output-sensitive manner. Clarkson and Shor proposed an optimal randomized algorithm for this problem, with an expected running time O(n log h), where h denotes the number of points on the surface of the convex hull. In this note we point out that the algorithm can be made deterministic by using recently developed techniques, thus obtaining an optimal deterministic algorithm.",

keywords = "Computational complexity, Computational geometry, Convex hull, Randomized algorithm",

author = "Bernard Chazelle and Ji{\v r}{\'i} Matou{\v s}ek",

note = "Funding Information: * Corresponding author. 1 Work by Bernard Chazelle has been supported by NSF Grant CCR-90-02352 and the Geometry Center.",

year = "1995",

month = mar,

doi = "10.1016/0925-7721(94)00018-Q",

language = "English (US)",

volume = "5",

pages = "27--32",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Derandomizing an output-sensitive convex hull algorithm in three dimensions

AU - Chazelle, Bernard

AU - Matoušek, Jiří

N1 - Funding Information: * Corresponding author. 1 Work by Bernard Chazelle has been supported by NSF Grant CCR-90-02352 and the Geometry Center.

PY - 1995/3

Y1 - 1995/3

N2 - We consider the computation of the convex hull of a given n-point set in three-dimensional Euclidean space in an output-sensitive manner. Clarkson and Shor proposed an optimal randomized algorithm for this problem, with an expected running time O(n log h), where h denotes the number of points on the surface of the convex hull. In this note we point out that the algorithm can be made deterministic by using recently developed techniques, thus obtaining an optimal deterministic algorithm.

AB - We consider the computation of the convex hull of a given n-point set in three-dimensional Euclidean space in an output-sensitive manner. Clarkson and Shor proposed an optimal randomized algorithm for this problem, with an expected running time O(n log h), where h denotes the number of points on the surface of the convex hull. In this note we point out that the algorithm can be made deterministic by using recently developed techniques, thus obtaining an optimal deterministic algorithm.

KW - Computational complexity

KW - Computational geometry

KW - Convex hull

KW - Randomized algorithm

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

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

U2 - 10.1016/0925-7721(94)00018-Q

DO - 10.1016/0925-7721(94)00018-Q

M3 - Article

AN - SCOPUS:0040358066

SN - 0925-7721

VL - 5

SP - 27

EP - 32

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 1

ER -

Derandomizing an output-sensitive convex hull algorithm in three dimensions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this