TY - JOUR
T1 - Applied computational geometry
T2 - Towards robust solutions of basic problems
AU - Dobkin, David
AU - Silver, Deborah
N1 - Funding Information:
As is the rule in computational geometry problems with discrete output, we assume all the computations are performed with exact (infinite-precision) arithmetic. Without this assumption it is virtually impossible to prove the correctness of any geometric algorithms. [MS873 * This work was supported in part by a National Science Foundation a Hewlett-Packard Faculty Development Grant to the second author.
Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 1990/2
Y1 - 1990/2
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0025384374&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025384374&partnerID=8YFLogxK
U2 - 10.1016/0022-0000(90)90019-H
DO - 10.1016/0022-0000(90)90019-H
M3 - Article
AN - SCOPUS:0025384374
VL - 40
SP - 70
EP - 87
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
SN - 0022-0000
IS - 1
ER -