EXACT AND OPTIMAL CONVEX HULLS IN 2D

DOI10.1142/S0218195900000085zbMATH Open1074.68649MaRDI QIDQ4682192FDOQ4682192

Authors: H. Ratschek, J. Rokne 

Publication date: 10 June 2005

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

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

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)

Cites Work

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

Cited In (6)

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

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)