A filtering technique for fast convex hull construction in R^2

DOI10.1016/J.CAM.2019.06.014MaRDI QIDQ2279854zbMATH OpenOpenAlexFDO

Authors Héctor Ferrada, Nancy Hitschfeld, Cristobal A. Navarro

Publication date 16 December 2019

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cam.2019.06.014

zbMATH Keywords

convex hullfiltering techniquepriority queues

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in \(\mathbb{R}^n\)
• Algorithms to determine the edges of a convex hull from its vertices
• gHull, a GPU algorithm for 3D convex hull
• A fast algorithm to decide the inclusion of a point in the convex hull of a two-dimensional point set
• An efficient convex hull algorithm using affine transformation in planar point set

Cites work

• A constant-time parallel algorithm for computing convex hulls
• A fast convex hull algorithm
• A Lower Bound to Finding Convex Hulls
• An Algorithm for Convex Polytopes
• An efficient algorithm for determining the convex hull of a finite planar set
• Another efficient algorithm for convex hulls in two dimensions
• Convex hull of a finite set of points in two dimensions
• Convex hulls of finite sets of points in two and three dimensions
• Efficient parallel convex hull algorithms
• Encyclopedia of Distances
• Finding minimal enclosing boxes
• gHull, a GPU algorithm for 3D convex hull
• scientific article; zbMATH DE number 3887061 (Why is no real title available?)
• Introduction to algorithms.
• On the identification of the convex hull of a finite set of points in the plane
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• The complexity of incremental convex hull algorithms in \(R^ d\)
• The quickhull algorithm for convex hulls
• The Ultimate Planar Convex Hull Algorithm?

Cited in

(4)

• scientific article; zbMATH DE number 5984563 (Why is no real title available?)
• Inner -approximation of the convex hull of finite sets
• Octagonal and hexadecagonal cut algorithms for finding the convex hull of finite sets with linear time complexity
• Methods for identifying all extreme points of convex hulls in spaces of dimension greater than 3 revisited

Describes a project that uses

Uses Software

• CGAL
• Qhull
• 3D Convex Hulls

This page was built for publication: A filtering technique for fast convex hull construction in \(\mathbb{R}^2\)

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