A Complete Implementation for Computing General Dimensional Convex Hulls

DOI10.1142/S0218195998000126zbMath1035.68529MaRDI QIDQ4513209

Ioannis Z. Emiris

Publication date: 7 November 2000

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

robustnesspostprocessinginfinitesimal perturbationBeneath-Beyond algorithm

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Early termination in sparse interpolation algorithms ⋮ Efficient Predicate Evaluation Using Randomized Degeneracy Detection ⋮ Computing the sign or the value of the determinant of an integer matrix, a complexity survey. ⋮ Improved algorithms for computing determinants and resultants ⋮ Real-time fuzzy regression analysis: a convex hull approach ⋮ Rational univariate reduction via toric resultants

Uses Software

• Hull

Cites Work

• Four results on randomized incremental constructions
• Matrix multiplication via arithmetic progressions
• A geometric consistency theorem for a symbolic perturbation scheme
• Fast algorithms for the characteristic polynomial
• Computing a ham-sandwich cut in two dimensions
• Edge-skeletons in arrangements with applications
• Small-dimensional linear programming and convex hulls made easy
• Applications of random sampling to on-line algorithms in computational geometry
• Multipolynomial resultant algorithms
• Applications of random sampling in computational geometry. II
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• Symbolic treatment of geometric degeneracies
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• On the Average Number of Maxima in a Set of Vectors and Applications
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• A General Approach to Removing Degeneracies