Output-sensitive results on convex hulls, extreme points, and related problems
From MaRDI portal
Publication:1816463
DOI10.1007/BF02712874zbMath0857.68112MaRDI QIDQ1816463
Publication date: 3 March 1997
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Related Items (22)
Robust vertex enumeration for convex hulls in high dimensions ⋮ A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes ⋮ Approximating points by a piecewise linear function ⋮ APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS ⋮ Combinatorial redundancy detection ⋮ Optimal, output-sensitive algorithms for constructing planar hulls in parallel ⋮ Space-efficient planar convex hull algorithms ⋮ Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs ⋮ Competing output-sensitive frame algorithms ⋮ Optimal partition trees ⋮ Approximate Polytope Membership Queries ⋮ Convex hulls of spheres and convex hulls of disjoint convex polytopes ⋮ A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations ⋮ FINDING SIMPLICES CONTAINING THE ORIGIN IN TWO AND THREE DIMENSIONS ⋮ Outlier respecting points approximation ⋮ On approximate range counting and depth ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ Solving degenerate sparse polynomial systems faster ⋮ Optimal output-sensitive convex hull algorithms in two and three dimensions ⋮ Economical Delone Sets for Approximating Convex Bodies ⋮ A characterization theorem and an algorithm for a convex hull problem ⋮ On constant factors in comparison-based geometric algorithms and data structures
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On ray shooting in convex polytopes
- Fast detection of polyhedral intersection
- On the detection of a common intersection of k convex subjects in the plane
- Maintenance of configurations in the plane
- Small-dimensional linear programming and convex hulls made easy
- Cutting hyperplanes for divide-and-conquer
- \(k\)-violation linear programming
- Derandomizing an output-sensitive convex hull algorithm in three dimensions
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- Applications of random sampling in computational geometry. II
- Dynamic half-space range reporting and its applications
- An efficient algorithm for determining the convex hull of a finite planar set
- Ray Shooting and Parametric Search
- An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- Finding the convex hull facet by facet
- On the convex layers of a planar set
- The Ultimate Planar Convex Hull Algorithm?
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Linear Programming in Linear Time When the Dimension Is Fixed
- Decomposable searching problems I. Static-to-dynamic transformation
- Convex hulls of finite sets of points in two and three dimensions
- On the Average Number of Maxima in a Set of Vectors and Applications
- Enumerating extreme points in higher dimensions
- Slowing down sorting networks to obtain faster sorting algorithms
- Linear Optimization Queries
- Constructing Belts in Two-Dimensional Arrangements with Applications
- A combinatorial bound for linear programming and related problems
- Sur L'enveloppe convexe des nuages de points aleatoires dans Rn. I
- An Algorithm for Convex Polytopes
- The maximum numbers of faces of a convex polytope
This page was built for publication: Output-sensitive results on convex hulls, extreme points, and related problems
