Small-dimensional linear programming and convex hulls made easy
From MaRDI portal
Publication:1176319
DOI10.1007/BF02574699zbMath0747.90066OpenAlexW1990970199WikidataQ114830763 ScholiaQ114830763MaRDI QIDQ1176319
Publication date: 25 June 1992
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131168
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)
Related Items
A LIBRARY FOR DOING POLYHEDRAL OPERATIONS, Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points, Randomized algorithms for the separation of point sets and for solving quadratic programs, Convex hulls, oracles, and homology, APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS, A PARALLEL ALGORITHM FOR FIXED-DIMENSIONAL LINEAR PROGRAMMING∗, Efficient piecewise-linear function approximation using the uniform metric, Linear programming, the simplex algorithm and simple polytopes, Space-efficient planar convex hull algorithms, Average case analysis of dynamic geometric optimization, An algorithm for constructing the convex hull of a set of spheres in dimension \(d\), Point location in zones of \(k\)-flats in arrangements, Randomized geometric algorithms and pseudorandom generators, A subexponential bound for linear programming, Lower bounds for a subexponential optimization algorithm, A combinatorial bound for linear programming and related problems, Geometric pattern matching in d-dimensional space, Random sampling with removal, Helly’s theorem: New variations and applications, Prune-and-search with limited workspace, Unique sink orientations of grids, An introduction to randomized algorithms, Markov incremental constructions, A quick negative selection algorithm for one-class classification in big data era, On ray shooting in convex polytopes, Two-variable linear programming in parallel, Some Discrete Properties of the Space of Line Transversals to Disjoint Balls, Unnamed Item, Two-variable linear programming in parallel, Stabbing pairwise intersecting disks by five points, On lazy randomized incremental construction, Generation of dangerous disturbances for flight systems, SUPERIMPOSING VORONOI COMPLEXES FOR SHAPE DEFORMATION, A unified approach to tail estimates for randomized incremental construction, Output-sensitive results on convex hulls, extreme points, and related problems, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, General models in min-max planar location: Checking optimality conditions, Complexity of projected images of convex subdivisions, A characterization theorem and an algorithm for a convex hull problem, An optimal convex hull algorithm in any fixed dimension, Optimal Algorithms for Geometric Centers and Depth, A Complete Implementation for Computing General Dimensional Convex Hulls
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Applications of random sampling in computational geometry. II
- A randomized algorithm for fixed-dimensional linear programming
- Linear programming in \(O(n\times 3^{d^2})\) time
- An efficient algorithm for determining the convex hull of a finite planar set
- Linear Time Algorithms for Two- and Three-Variable Linear Programs
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- Finding the convex hull facet by facet
- Linear Programming in Linear Time When the Dimension Is Fixed
- Convex hulls of finite sets of points in two and three dimensions
- On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
- An Algorithm for Convex Polytopes
- The maximum numbers of faces of a convex polytope
