Applied computational geometry: Towards robust solutions of basic problems

David Dobkin, Deborah Silver

Research output: Contribution to journalArticle

17 Scopus citations

Abstract

Geometric computations, like all numerical procedures, are extremely prone to roundoff error. However, virtually none of the numerical analysis literature directly applies to geometric calculations. Even for line intersection, the most basic geometric operation, there is no robust and efficient algorithm. Compounding the difficulties, many geometric algorithms perform iterations of calculations reusing previously computed data. In this paper, we explore some of the main issues in geometric computations and the methods that have been proposed to handle roundoff errors. In particular, we focus on one method and apply it to a general iterative intersection problem. Our initial results seem promising and will hopefully lead to robust solutions for more complex problems of applied computational geometry.

Original languageEnglish (US)
Pages (from-to)70-87
Number of pages18
JournalJournal of Computer and System Sciences
Volume40
Issue number1
DOIs
StatePublished - Feb 1990

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Applied computational geometry: Towards robust solutions of basic problems'. Together they form a unique fingerprint.

Cite this