Towards exact geometric computation

Research output: Contribution to journalArticlepeer-review

Abstract

Exact computation is assumed in most algorithms in computational geometry. In practice, implementors perform computation in some fixed-precision model, usually the machine floating-point arithmetic. Such implementations have many well-known problems, here informally called "robustness issues"". To reconcile theory and practice, authors have suggested that theoretical algorithms ought to be redesigned to become robust under fixed-precision arithmetic. We suggest that in many cases, implementors should make robustness a non-issue by computing exactly. The advantages of exact computation are too many to ignore. Many of the presumed difficulties of exact computation are partly surmountable and partly inherent with the robustness goal. This paper formulates the theoretical framework for exact computation based on algebraic numbers. We then examine the practical support needed to make the exact approach a viable alternative. It turns out that the exact computation paradigm encompasses a rich set of computational tactics. Our fundamental premise is that the traditional "BigNumber" package that forms the work-horse for exact computation must be reinvented to take advantage of many features found in geometric algorithms. Beyond this, we postulate several other packages to be built on top of the BigNumber package.

Original languageEnglish (US)
Pages (from-to)3-23
Number of pages21
JournalComputational Geometry: Theory and Applications
Volume7
Issue number1-2
DOIs
StatePublished - Jan 1997

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Towards exact geometric computation'. Together they form a unique fingerprint.

Cite this