Derandomizing an output-sensitive convex hull algorithm in three dimensions

DOI10.1016/0925-7721(94)00018-QzbMath0814.68127OpenAlexW1987576325MaRDI QIDQ1346251

Bernard Chazelle, Ji{ří} Matoušek

Publication date: 22 March 1995

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(94)00018-q

zbMATH Keywords

optimal rnadomized algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (3) dimensions (including convex surfaces) (52A15)

Related Items (10)

The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs ⋮ Convex hulls of spheres and convex hulls of disjoint convex polytopes ⋮ Fast randomized parallel methods for planar convex hull construction ⋮ Hausdorff approximation of 3D convex polytopes ⋮ Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection ⋮ Optimal output-sensitive convex hull algorithms in two and three dimensions ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ An optimal convex hull algorithm in any fixed dimension ⋮ Linear time approximation of 3D convex polytopes ⋮ On constant factors in comparison-based geometric algorithms and data structures

Cites Work

• Unnamed Item
• Efficient partition trees
• An optimal convex hull algorithm in any fixed dimension
• Applications of random sampling in computational geometry. II
• An efficient algorithm for determining the convex hull of a finite planar set
• An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• The Ultimate Planar Convex Hull Algorithm?
• Linear Programming in Linear Time When the Dimension Is Fixed
• Optimal Search in Planar Subdivisions
• Convex hulls of finite sets of points in two and three dimensions
• Linear Optimization Queries

This page was built for publication: Derandomizing an output-sensitive convex hull algorithm in three dimensions