Computing convex hull in a floating point arithmetic
type: Item
instance of: scholarly article
title: Computing convex hull in a floating point arithmetic
zbMATH Open document ID: 0809.65148
DOI: 10.1016/0925-7721(94)00017-4
published in: Computational Geometry
publication date: 1994-11-30T00:00:00Z
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\).
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 52A10
zbMATH DE Number: 682493
zbMATH Keywords: convex hulls
zbMATH Keywords: floating point algorithm
zbMATH Keywords: algorithm \({\mathbf{Convex}}\)
author: Jerzy W. Jaromczyk
author: Grzegorz W. Wasilkowski
reviewed by: Heinrich Guggenheimer
MaRDI profile type: Publication
full work available at URL: 0925-7721(94)00017-4
OpenAlex ID: W2082233487
cites work: Q3772828
cites work: Numerical stability of a convex hull algorithm for simple polygons
cites work: Q3992847
description: scientific article; zbMATH DE number 682493