An optimal convex hull algorithm in any fixed dimension

Bernard Chazelle

doi:10.1007/BF02573985

An optimal convex hull algorithm in any fixed dimension

Bernard Chazelle

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

260 Scopus citations

Abstract

We present a deterministic algorithm for computing the convex hull of n points in E^d in optimal O(n log n+n^{{down left corner}d/2{down right corner}} ) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an algorithm for computing the Voronoi diagram of n points in d-space in optimal O(n log n+n^{{top left corner}d/2{top right corner}} ) time.

Original language	English (US)
Pages (from-to)	377-409
Number of pages	33
Journal	Discrete & Computational Geometry
Volume	10
Issue number	1
DOIs	https://doi.org/10.1007/BF02573985
State	Published - Dec 1993
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/BF02573985

Cite this

@article{f93be6fef74d42d6a5d4a2618b39c1af,

title = "An optimal convex hull algorithm in any fixed dimension",

abstract = "We present a deterministic algorithm for computing the convex hull of n points in E d in optimal O(n log n+n {down left corner}d/2{down right corner} ) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an algorithm for computing the Voronoi diagram of n points in d-space in optimal O(n log n+n {top left corner}d/2{top right corner} ) time.",

author = "Bernard Chazelle",

year = "1993",

month = dec,

doi = "10.1007/BF02573985",

language = "English (US)",

volume = "10",

pages = "377--409",

journal = "Discrete & Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - An optimal convex hull algorithm in any fixed dimension

AU - Chazelle, Bernard

PY - 1993/12

Y1 - 1993/12

N2 - We present a deterministic algorithm for computing the convex hull of n points in E d in optimal O(n log n+n {down left corner}d/2{down right corner} ) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an algorithm for computing the Voronoi diagram of n points in d-space in optimal O(n log n+n {top left corner}d/2{top right corner} ) time.

AB - We present a deterministic algorithm for computing the convex hull of n points in E d in optimal O(n log n+n {down left corner}d/2{down right corner} ) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an algorithm for computing the Voronoi diagram of n points in d-space in optimal O(n log n+n {top left corner}d/2{top right corner} ) time.

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

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

U2 - 10.1007/BF02573985

DO - 10.1007/BF02573985

M3 - Article

AN - SCOPUS:51249162153

SN - 0179-5376

VL - 10

SP - 377

EP - 409

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 1

ER -

An optimal convex hull algorithm in any fixed dimension

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this