Computing convex hull in a floating point arithmetic

Jerzy W. Jaromczyk; G. W. Wasilkowski

doi:10.1016/0925-7721(94)00017-4

Computing convex hull in a floating point arithmetic

Jerzy W. Jaromczyk, G. W. Wasilkowski

Computer Science

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

We present an algorithm which is numerically stable and optimal in time and space complexity for constructing the convex hull for a set of points on a plane. In contrast to existing numerically stable algorithms which return only an approximate hull, our algorithm constructs a polygon that is truly convex. The algorithm is simple and easy to implement. We assume a floating point arithmetic as a computation model.

Original language	English
Pages (from-to)	283-292
Number of pages	10
Journal	Computational Geometry: Theory and Applications
Volume	4
Issue number	5
DOIs	https://doi.org/10.1016/0925-7721(94)00017-4
State	Published - Oct 1994

Keywords

Convex hull
Numerical stability

ASJC Scopus subject areas

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/0925-7721(94)00017-4

Cite this

@article{b3d19838a30a4b67ae02ce31556cc0ce,

title = "Computing convex hull in a floating point arithmetic",

abstract = "We present an algorithm which is numerically stable and optimal in time and space complexity for constructing the convex hull for a set of points on a plane. In contrast to existing numerically stable algorithms which return only an approximate hull, our algorithm constructs a polygon that is truly convex. The algorithm is simple and easy to implement. We assume a floating point arithmetic as a computation model.",

keywords = "Convex hull, Numerical stability",

author = "Jaromczyk, {Jerzy W.} and Wasilkowski, {G. W.}",

year = "1994",

month = oct,

doi = "10.1016/0925-7721(94)00017-4",

language = "English",

volume = "4",

pages = "283--292",

number = "5",

}

TY - JOUR

T1 - Computing convex hull in a floating point arithmetic

AU - Jaromczyk, Jerzy W.

AU - Wasilkowski, G. W.

PY - 1994/10

Y1 - 1994/10

N2 - We present an algorithm which is numerically stable and optimal in time and space complexity for constructing the convex hull for a set of points on a plane. In contrast to existing numerically stable algorithms which return only an approximate hull, our algorithm constructs a polygon that is truly convex. The algorithm is simple and easy to implement. We assume a floating point arithmetic as a computation model.

AB - We present an algorithm which is numerically stable and optimal in time and space complexity for constructing the convex hull for a set of points on a plane. In contrast to existing numerically stable algorithms which return only an approximate hull, our algorithm constructs a polygon that is truly convex. The algorithm is simple and easy to implement. We assume a floating point arithmetic as a computation model.

KW - Convex hull

KW - Numerical stability

UR - http://www.scopus.com/inward/record.url?scp=0346777695&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346777695&partnerID=8YFLogxK

U2 - 10.1016/0925-7721(94)00017-4

DO - 10.1016/0925-7721(94)00017-4

M3 - Article

AN - SCOPUS:0346777695

SN - 0925-7721

VL - 4

SP - 283

EP - 292

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 5

ER -

Computing convex hull in a floating point arithmetic

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this