Robust geometric computation

Vikram Sharma, Chee K. Yap

Research output: Chapter in Book/Report/Conference proceedingChapter


Nonrobustness refers to qualitative or catastrophic failures in geometric algorithms arising from numerical errors. Section 45.1 provides background on these problems. Although nonrobustness is already an issue in “purely numerical” computation, the problem is compounded in “geometric computation.” In Section 45.2 we characterize such computations. Researchers trying to create robust geometric software have tried two approaches: making fixed-precision computation robust (Section 45.3), and making the exact approach viable (Section 45.4). Another source of nonrobustness is the phenomenon of degenerate inputs. General methods for treating degenerate inputs are described in Section 45.5. For some problems the exact approach may be expensive or infeasible. To ensure robustness in this setting, a recent extension of exact computation, the so-called “soft exact approach,” has been proposed. This is described in Section 45.6.

Original languageEnglish (US)
Title of host publicationHandbook of Discrete and Computational Geometry, Third Edition
PublisherCRC Press
Number of pages35
ISBN (Electronic)9781498711425
ISBN (Print)9781498711395
StatePublished - Jan 1 2017

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


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

Cite this