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

DOI10.1137/0220016zbMath0722.68064OpenAlexW2065697367MaRDI QIDQ3210183

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

convex hullthree dimensionscomputational geometryoutput sensitive

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Derandomizing an output-sensitive convex hull algorithm in three dimensions, A time-optimal parallel algorithm for three-dimensional convex hulls, Unnamed Item, Constructing the convex hull of a partially sorted set of points, Optimal output-sensitive convex hull algorithms in two and three dimensions, Output-sensitive results on convex hulls, extreme points, and related problems, An Output-Sensitive Convex Hull Algorithm for Planar Objects