Faster geometric algorithms via dynamic determinant computation

DOI10.1016/j.comgeo.2015.12.001zbMath1338.65118arXiv1206.7067OpenAlexW3104511711WikidataQ56041858 ScholiaQ56041858MaRDI QIDQ283878

Vissarion Fisikopoulos, Luis Mariano Peñaranda

Publication date: 17 May 2016

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

Full work available at URL: https://arxiv.org/abs/1206.7067

zbMATH Keywords

volumenumerical exampleconvex hullexperimental analysisdeterminant algorithmsorientation predicatepoint locationrank-1 updatesvolume computation

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical computation of determinants (65F40)

Related Items

\texttt{mplrs}: a scalable parallel vertex/facet enumeration code ⋮ Fast floating-point filters for robust predicates

Uses Software

• CGAL
• LinBox
• polymake
• TOPCOM
• Eigen
• triangulation
• Hull
• respol

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Implicitization of curves and (hyper)surfaces using predicted support
• Four results on randomized incremental constructions
• On computing the determinant in small parallel time using a small number of processors
• Faster combinatorial algorithms for determinant and Pfaffian
• Sign determination in residue number systems
• Computing the sign or the value of the determinant of an integer matrix, a complexity survey.
• On the complexity of computing determinants
• Applications of random sampling in computational geometry. II
• A simple division-free algorithm for computing determinants
• Efficient exact evaluation of signs of determinants
• Classroom examples of robustness problems in geometric computations
• Advanced determinant calculus: a complement
• AN ORACLE-BASED, OUTPUT-SENSITIVE ALGORITHM FOR PROJECTIONS OF RESULTANT POLYTOPES
• Faster Geometric Algorithms via Dynamic Determinant Computation
• Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix
• Powers of tensors and fast matrix multiplication
• Lectures on Polytopes
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Using Algebraic Geometry
• Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension
• The Effect of New Links on Google Pagerank
• Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
• An Algorithm for Convex Polytopes
• Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix
• An Inverse Matrix Adjustment Arising in Discriminant Analysis
• Algorithms in real algebraic geometry
• Interval arithmetic yields efficient dynamic filters for computational geometry

This page was built for publication: Faster geometric algorithms via dynamic determinant computation