EXACT AND OPTIMAL CONVEX HULLS IN 2D

DOI10.1142/S0218195900000085MaRDI QIDQ4682192zbMATHFDO

Authors H. Ratschek, J. Rokne

Publication date 10 June 2005

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

interval arithmeticConvex hullsexact computationsGraham scan

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) General methods in interval analysis (65G40)

Recommendations

• An efficient and numerically correct algorithm for the 2D convex hull problem
• Computing convex hull in a floating point arithmetic
• Finding the convex hull of a simple polygon
• The quickhull algorithm for convex hulls
• scientific article; zbMATH DE number 724218

Cites work

• A fast convex hull algorithm
• An efficient algorithm for determining the convex hull of a finite planar set
• An efficient and numerically correct algorithm for the 2D convex hull problem
• Another efficient algorithm for convex hulls in two dimensions
• Computing convex hull in a floating point arithmetic
• Exact computation of the sign of a finite sum
• Numerical stability of a convex hull algorithm for simple polygons

Cited in

(6)

• An efficient and numerically correct algorithm for the 2D convex hull problem
• Constructing strongly convex hulls using exact or rounded arithmetic
• Numerical stability of a convex hull algorithm for simple polygons
• A Complete Implementation for Computing General Dimensional Convex Hulls
• Using interval arithmetic for determining the structure of convex hulls
• A CONVEX HULL ALGORITHM FOR POINTS WITH APPROXIMATELY KNOWN POSITIONS

This page was built for publication: EXACT AND OPTIMAL CONVEX HULLS IN 2D

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