An O(n\log ^2 h) Time Algorithm for the Three-Dimensional Convex Hull Problem

DOI10.1137/0220016MaRDI QIDQ3210183zbMATH OpenOpenAlexFDO

Authors Weiping Shi, Herbert Edelsbrunner

Publication date 1991

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220016

zbMATH Keywords

computational geometryconvex hullthree dimensionsoutput sensitive

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A time-optimal parallel algorithm for three-dimensional convex hulls
• scientific article; zbMATH DE number 724218
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• The Ultimate Planar Convex Hull Algorithm?
• An efficient and numerically correct algorithm for the 2D convex hull problem

Cited in

(11)

• An efficient convex hull algorithm for finite point sets in 3D based on the method of orienting curves
• scientific article; zbMATH DE number 7561401 (Why is no real title available?)
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• A time-optimal parallel algorithm for three-dimensional convex hulls
• Output-sensitive results on convex hulls, extreme points, and related problems
• Computing hereditary convex structures
• scientific article; zbMATH DE number 123809 (Why is no real title available?)
• Constructing the convex hull of a partially sorted set of points
• An Output-Sensitive Convex Hull Algorithm for Planar Objects
• Derandomizing an output-sensitive convex hull algorithm in three dimensions
• scientific article; zbMATH DE number 4062600 (Why is no real title available?)

This page was built for publication: An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem

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