Computing convex hull in a floating point arithmetic

DOI10.1016/0925-7721(94)00017-4MaRDI QIDQ1337401zbMATH OpenOpenAlexFDO

Authors Jerzy W. Jaromczyk, Grzegorz W. Wasilkowski

Publication date 30 November 1994

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(94)00017-4

zbMATH Keywords

algorithm \({\mathbf{Convex}}\)convex hullsfloating point algorithm

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

Most known algorithms for computation of convex hulls presume exact arithmetic and may be unstable in finite precision arithmetic. A floating point algorithm like \textit{S. Fortune's} [Stable maintenance of point-set triangulations in two dimension, Proceedings 27th IEEE Symposium on Foundations of Computer Science, 494-499 (1989)] gives only approximate hulls that may not be convex. This paper presents an algorithm \({\mathbf{Convex}}\) that is numerically stable and extracts from the output of Fortune's algorithm a truly convex hull; the distances of the new points from the input points are well controlled at linear functions of machine precision \(u\).

Recommendations

• The quickhull algorithm for convex hulls
• Floating-point arithmetic for computational geometry problems with uncertain data
• An efficient and numerically correct algorithm for the 2D convex hull problem
• A CONVEX HULL ALGORITHM FOR POINTS WITH APPROXIMATELY KNOWN POSITIONS

Cites work

• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Numerical stability of a convex hull algorithm for simple polygons

Cited in

(18)

• Constructing strongly convex hulls using exact or rounded arithmetic
• Why does information-based complexity use the real number model?
• Exact computation of the sign of a finite sum
• Numerical stability of a convex hull algorithm for simple polygons
• Robust gift wrapping for the three-dimensional convex hull
• Euclidean minimum spanning trees with independent and dependent geometric uncertainties
• Fast and accurate floating point summation with application to computational geometry
• Using interval arithmetic for determining the structure of convex hulls
• Classroom examples of robustness problems in geometric computations
• Floating-point arithmetic for computational geometry problems with uncertain data
• Construction of the convex hull of a finite set of points when the computations are approximate
• Computing Two-Dimensional Integer Hulls
• A CONVEX HULL ALGORITHM FOR POINTS WITH APPROXIMATELY KNOWN POSITIONS
• The quickhull algorithm for convex hulls
• EXACT AND OPTIMAL CONVEX HULLS IN 2D
• Voronoi Diagram and Delaunay Triangulation with Independent and Dependent Geometric Uncertainties
• A Provably Robust Algorithm for Triangle-triangle Intersections in Floating-point Arithmetic
• Error control in polytope computations

This page was built for publication: Computing convex hull in a floating point arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1337401)