AN OPTIMAL CONVEX-HULL ALGORITHM IN ANY FIXED DIMENSION

Authors
CHAZELLE B
Citation
B. Chazelle, AN OPTIMAL CONVEX-HULL ALGORITHM IN ANY FIXED DIMENSION, Discrete & computational geometry, 10(4), 1993, pp. 377-409
Citations number
23
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, Pure","Computer Applications & Cybernetics",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
10
Issue
4
Year of publication
1993
Pages
377 - 409
Database
ISI
SICI code
0179-5376(1993)10:4<377:AOCAIA>2.0.ZU;2-N
Abstract
We present a deterministic algorithm for computing the convex hull of n points in E(d) in optimal O(n log n + n right perpendicular d/2 left perpendicular) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an al gorithm for computing the Voronoi diagram of n points in d-space in op timal O(n log n + n inverted right perpendicular d/2 inverted left per pendicular) time.