Table based detection of degenerate predicates in free space construction

DOI10.4230/LIPICS.SOCG.2018.61zbMATH Open1489.68368arXiv1803.06908OpenAlexW2963891080MaRDI QIDQ5116521FDOQ5116521

Authors: Victor J. Milenkovic, Elisha Sacks, Nabeel Butt 

Publication date: 18 August 2020

Abstract: The key to a robust and efficient implementation of a computational geometry algorithm is an efficient algorithm for detecting degenerate predicates. We study degeneracy detection in constructing the free space of a polyhedron that rotates around a fixed axis and translates freely relative to another polyhedron. The structure of the free space is determined by the signs of univariate polynomials, called angle polynomials, whose coefficients are polynomials in the coordinates of the vertices of the polyhedra. Every predicate is expressible as the sign of an angle polynomial $f$ evaluated at a zero $t$ of an angle polynomial $g$. A predicate is degenerate (the sign is zero) when $t$ is a zero of a common factor of $f$ and $g$. We present an efficient degeneracy detection algorithm based on a one-time factoring of every possible angle polynomial. Our algorithm is 3500 times faster than the standard algorithm based on greatest common divisor computation. It reduces the share of degeneracy detection in our free space computations from 90% to 0.5% of the running time.

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

Recommendations

• Fast detection of degenerate predicates in free space construction
• Symbolic treatment of geometric degeneracies
• A General Approach to Removing Degeneracies
• scientific article; zbMATH DE number 1003230
• scientific article; zbMATH DE number 6154261

zbMATH Keywords

robustnessdegenerate predicatesfree space construction

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Exact Minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces
• Planar shape manipulation using approximate geometric primitives
• Controlled Perturbation for Certified Geometric Computing with Fixed-Precision Arithmetic
• Fast detection of degenerate predicates in free space construction

Cited In (1)

• Fast detection of degenerate predicates in free space construction

Uses Software

• CGAL

This page was built for publication: Table based detection of degenerate predicates in free space construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116521)