Computing convex hull in a floating point arithmetic (Q1337401): Difference between revisions
From MaRDI portal
Removed claims |
ReferenceBot (talk | contribs) Changed an Item |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Property / author | |||
| Property / author: Jerzy W. Jaromczyk / rank | |||
Normal rank | |||
| Property / author | |||
| Property / author: Grzegorz W. Wasilkowski / rank | |||
Normal rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Heinrich Guggenheimer / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0925-7721(94)00017-4 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2082233487 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3772828 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Numerical stability of a convex hull algorithm for simple polygons / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3992847 / rank | |||
Normal rank | |||
Latest revision as of 10:15, 23 May 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computing convex hull in a floating point arithmetic |
scientific article |
Statements
Computing convex hull in a floating point arithmetic (English)
0 references
30 November 1994
0 references
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\).
0 references
convex hulls
0 references
floating point algorithm
0 references
algorithm \({\mathbf{Convex}}\)
0 references
