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
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
