×

Table based detection of degenerate predicates in free space construction. (English) Zbl 1489.68368

Speckmann, Bettina (ed.) et al., 34th international symposium on computational geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 99, Article 61, 14 p. (2018).
Summary: 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.
For the entire collection see [Zbl 1390.68027].

MSC:

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

Software:

CGAL
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Cgal, Computational Geometry Algorithms Library. http://www.cgal.org. ##img##
[2] Peter Hachenberger. Exact Minkowski sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces. Algorithmica, 55:329-345, 2009. ##img## · Zbl 1186.68500
[3] Dan Halperin. Controlled perturbation for certified geometric computing with fixed-precision arithmetic. In ICMS, pages 92-95, 2010. ##img## · Zbl 1295.65019
[4] Min-Ho Kyung, Elisha Sacks, and Victor Milenkovic. Robust polyhedral Minkowski sums with GPU implementation. Computer-Aided Design, 67-68:48-57, 2015. ##img##
[5] Naama Mayer, Efi Fogel, and Dan Halperin. Fast and robust retrieval of Minkowski sums of rotating convex polyhedra in 3-space. Computer-Aided Design, 43(10):1258-1269, 2011. ##img##
[6] Victor Milenkovic, Elisha Sacks, and Steven Trac. Robust free space computation for curved planar bodies. IEEE Transactions on Automation Science and Engineering, 10(4):875-883, 2013. ##img## · Zbl 1327.68320
[7] Elisha Sacks, Nabeel Butt, and Victor Milenkovic. Robust free space construction for a polyhedron with planar motion. Computer-Aided Design, 90C:18-26, 2017. ##img## · Zbl 1493.68373
[8] Elisha Sacks and Victor Milenkovic. Robust cascading of operations on polyhedra. Computer-Aided Design, 46:216-220, 2014. ##img##
[9] J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, 1980. URL: http://dx.doi.org/10.1145/322217.322225. · Zbl 0452.68050 · doi:10.1145/322217.322225
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.