An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in R^n

DOI10.1007/S11075-020-00873-1zbMATH Open1457.65011OpenAlexW3012620846MaRDI QIDQ827092FDOQ827092

Phan Thanh An, Nam Dũng Hoàng, Nguyen Kieu Linh

Publication date: 6 January 2021

Published in: Numerical Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11075-020-00873-1

Recommendations

• An efficient convex hull algorithm for finite point sets in 3D based on the method of orienting curves
• scientific article
• scientific article
• A new representation and algorithm for constructing convex hulls in higher dimensional spaces
• Robust gift wrapping for the three-dimensional convex hull

zbMATH Keywords

convex hull computationgift wrapping algorithmorienting curves method

Mathematics Subject Classification ID

Numerical interpolation (65D05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Cites Work

• QuickhullDisk: a faster convex hull algorithm for disks
• An efficient algorithm for determining the convex hull of a finite planar set
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Title not available (Why is that?)
• A New Convex Hull Algorithm for Planar Sets
• An Algorithm for Convex Polytopes
• Computational Geometry in C
• Convex hull of a finite set of points in two dimensions
• Convex Polytopes
• The Ultimate Planar Convex Hull Algorithm?
• An efficient convex hull algorithm for finite point sets in 3D based on the Method of Orienting Curves
• A parallel algorithm based on convexity for the computing of Delaunay tessellation
• Robust gift wrapping for the three-dimensional convex hull
• The complexity of incremental convex hull algorithms in \(R^ d\)
• On the upper-bound conjecture for convex polytopes
• Solving a class of optimal control problems which are linear in the control variable by the method of orienting curves
• Quicker than Quickhull
• Method of orienting curves for solving optimal control problems with state constraints¹
• Solving a class of regular optimal control problems with state constraints by the method of orienting curves
• Zur lösung einer regulären aufgabenklasse der optimalen steuerung im groβen mittels orientierungskurven
• Some remarks on the method of orienting curves^∗
• A convex Hull algorithm for solving a location problem
• Convex hull based skew estimation

Cited In (3)

• Title not available (Why is that?)
• A modified Graham's convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set
• Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points

Uses Software

• Qhull
• QuickhullDisk

This page was built for publication: An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in \(\mathbb{R}^n\)

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