An efficient and numerically correct algorithm for the 2D convex hull problem

DOI10.1007/BF02017351zbMath0707.65110OpenAlexW1972379785MaRDI QIDQ919797

Gary D. Knott, Thomas Chiungtung Kao

Publication date: 1990

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02017351

zbMATH Keywords

interval arithmetic2D convex hull problemboundary of the convex hullbucketing techniquesfinite set of pointsMerge Hull algorithmmultiple precision arithmeticplane convex hull algorithmspoint elimination techniquesworst-case running time behaviour

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Interval and finite arithmetic (65G30) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items (4)

An auxiliary theorem for stability analysis in the presence of interval- valued parameters ⋮ EXACT AND OPTIMAL CONVEX HULLS IN 2D ⋮ Convex hull of a planar set of straight and circular line segments ⋮ Exact computation of the sign of a finite sum

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Delaunay triangulation and the convex hull of n points in expected linear time
• Some performance tests of convex hull algorithms
• A fast convex hull algorithm
• Divide and conquer for linear expected time
• An efficient algorithm for determining the convex hull of a finite planar set
• On the identification of the convex hull of a finite set of points in the plane
• Constructing the convex hull of a set of points in the plane
• The Ultimate Planar Convex Hull Algorithm?
• A fast approximation to a convex hull
• Approximation algorithms for convex hulls
• A New Convex Hull Algorithm for Planar Sets

This page was built for publication: An efficient and numerically correct algorithm for the 2D convex hull problem