A simple algorithm for building the 3-D convex hull

DOI10.1007/BF02218436MaRDI QIDQ2266570zbMATH OpenOpenAlexFDO

Authors Gunner Helweg Johansen, Chr. Gram

Publication date 1983

Published in BIT (Search for Journal in Brave)

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

zbMATH Keywords

complexity boundsconvex hullminimum convex polyhedronstepwise refinement

Mathematics Subject Classification ID

Convex sets in (3) dimensions (including convex surfaces) (52A15) Numerical mathematical programming methods (65K05) Computer aspects of numerical algorithms (65Yxx) Linear programming (90C05)

Review text

This paper discusses an algorithm for finding the convex hull of a finite set of distinct points in 3-dimensional space. The algorithm is described at a 'high-level' and theoretical complexity bounds are discussed; however, no experimental results are provided.

Recommendations

• Combinatorial Image Analysis
• The implementation of an algorithm to find the convex hull of a set of three-dimensional points
• Shortest path on a non-convex polyhedron
• Algorithms to determine the edges of a convex hull from its vertices
• Construction of the convex hull of a point set as a system of linear inequalities

Cites work

• An Algorithm for Convex Polytopes
• Convex hulls of finite sets of points in two and three dimensions
• Divide and conquer for linear expected time
• scientific article; zbMATH DE number 3574936 (Why is no real title available?)
• On the identification of the convex hull of a finite set of points in the plane

Cited in

(4)

• The implementation of an algorithm to find the convex hull of a set of three-dimensional points
• scientific article; zbMATH DE number 7499212 (Why is no real title available?)
• An algorithm for intersections determination among geometric buffers using skip lists
• A multi-dimensional unified concavity and convexity detection method based on geometric algebra

This page was built for publication: A simple algorithm for building the 3-D convex hull

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