Numerical stability of a convex hull algorithm for simple polygons

J. W. Jaromczyk, G. W. Wasilkowski

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


A numerically stable and optimal O(n)-time implementation of an algorithm for finding the convex hull of a simple polygon is presented. Stability is understood in the sense of a backward error analysis. A concept of the condition number of simple polygons and its impact on the performance of the algorithm is discussed. It is shown that if the condition number does not exceed (1+O(ε))/(3 ε), then, in floating-point arithmetic with the unit roundoff ε, the algorithm produces the vertices of a convex hull for slightly perturbed input points. The relative perturbation does not exceed 3 ε(1+O(ε)).

Original languageEnglish
Pages (from-to)457-472
Number of pages16
Issue number6
StatePublished - Dec 1993


  • Convex hull
  • Floating-point arithmetic
  • Robust implementation
  • Simple polygon

ASJC Scopus subject areas

  • Computer Science (all)
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Numerical stability of a convex hull algorithm for simple polygons'. Together they form a unique fingerprint.

Cite this