PRECISE
PRECISE: Efficient multiprecision evaluation of algebraic roots and predicates for reliable geometric computation. Many geometric problems like generalized Voronoi diagrams, medial axis computations and boundary evaluation involve computation and manipulation of non-linear algebraic primitives like curves and surfaces. The algorithms designed for these problems make decisions based on signs of geometric predicates or on the roots of polynomials characterizing the problem. The reliability of the algorithm depends on the accurate evaluation of these signs and roots. In this paper, we present a naive precision-driven computational model to perform these computations reliably and demonstrate its effectiveness on a certain class of problems like sign of determinants with rational entries, boundary evaluation and curve arrangements. We also present a novel algorithm to compute all the roots of a univariate polynomial to any desired accuracy. The computational model along with the underlying number representation, precision-driven arithmetic and all the algorithms are implemented as part of a stand-alone software library, PRECISE.
This software is also peer reviewed by journal TOMS.
This software is also peer reviewed by journal TOMS.
Keywords for this software
References in zbMATH (referenced in 6 articles , 1 standard article )
Showing results 1 to 6 of 6.
Sorted by year (- Sagraloff, Michael; Kerber, Michael; Hemmer, Michael: Certified complex root isolation via adaptive root separation bounds (2009)
- Rump, Siegfried M.; Ogita, Takeshi; Oishi, Shinâ€™ichi: Accurate floating-point summation. I: Faithful rounding (2008)
- Culver, Tim; Keyser, John; Manocha, Dinesh: Exact computation of the medial axis of a polyhedron (2004)
- Culver, Tim; Keyser, John; Manocha, Dinesh; Krishnan, Shankar: A hybrid approach for determinant signs of moderate-sized matrices. (2003)
- Krishnan, Shankar; Foskey, Mark; Culver, Tim; Keyser, John; Manocha, Dinesh: PRECISE: efficient multiprecision evaluation of algebraic roots and predicates for reliable geometric computation (2001)
- Krishnan, S.; Manocha, D.; Gopi, M.; Culver, T.; Keyser, J.: Boole: a boundary evaluation system for Boolean combinations of sculptured solids (2001)