Verifiable implementations of geometric algorithms using finite precision arithmetic
作者:
摘要
Two methods are proposed for correct and verifiable geometric reasoning using finite precision arithmetic. The first method, data normalization, transforms the geometric structure into a configuration for which all finite precision calculations yield correct answers. The second method, called the hidden variable method, constructs configurations that belong to objects in an infinite precision domain—without actually representing these infinite precision objects. Data normalization is applied to the problem of modeling polygonal regions in the plane, and the hidden variable method is used to calculate arrangements of lines.
论文关键词:
论文评审过程:Available online 11 February 2003.
论文官网地址:https://doi.org/10.1016/0004-3702(88)90061-6