PRECISE: Efficient multiprecision evaluation of algebraic roots and predicates for reliable geometric computation Conference Paper uri icon

abstract

  • 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, P RECISE.

published proceedings

  • Proceedings of the Annual Symposium on Computational Geometry

author list (cited authors)

  • Krishnan, S., Foskey, M., Culver, T., Keyser, J., & Manocha, D.

complete list of authors

  • Krishnan, S||Foskey, M||Culver, T||Keyser, J||Manocha, D

publication date

  • January 2001