Derandomizing an output-sensitive convex hull algorithm in three dimensions

Bernard Chazelle, Jiří Matoušek

Research output: Contribution to journalArticlepeer-review

22 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 languageEnglish (US)
Pages (from-to)27-32
Number of pages6
JournalComputational Geometry: Theory and Applications
Volume5
Issue number1
DOIs
StatePublished - Mar 1995

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

Fingerprint Dive into the research topics of 'Derandomizing an output-sensitive convex hull algorithm in three dimensions'. Together they form a unique fingerprint.

Cite this