几何稳健性讲义(1)- 什么是几何稳健性?

translation geometry robust

关键词翻译

1. 几何稳健性

Most geometric algorithms are not designed for numerical robustness; they are based on the real RAM model, in which quantities are allowed to be arbitrary real numbers, and all arithmetic is exact. There are several ways a geometric algorithm that is correct within the real RAM model can go wrong in an encounter with a modern microprocessor, in which floating-point operations are subject to roundoff error. The output might be incorrect, but be correct for some perturbation of the input. The result might be usable yet not be valid for any imaginable input. Or, the program may simply crash or fail to produce a result. I occasionally hear of implementations where more than half the developers’ time is spent solving problems of roundoff error. For surveys of geometric robustness, see Fortune [9] and Hoffmann [15].

大多数的几何算法都是基于实数内存模型设计的, 所以达不到数值稳健的目的. 因为在实数内存模型中, 允许数量是任意的实数, 且所有的算法都是精确的, 而现代微处理器中的浮点操作会受舍入误差的影响. 在实数内存模型中正确的算法在现代微处理器中可以发生多种方式的错误. 如输出结果可能不正确, 但对于输入的某些扰动来说却是正确的. 输出结果也许可用, 但并不是对所有可以想像的输入都是有效的. 或者程序会直接崩溃掉,产生不了任何结果. 我偶尔听说在算法实施中, 开发者有超过一半的时间花在解决舍入误差的问题上. 关于几何稳健性的调查报告, 见文献 Fortune [9] 和 Hoffmann [15].

There are two types of geometric calculations, or primitives, found in geometric algorithms: predicates, which make a two-way or three-way decision (does this point lie to the left of, to the right of, or on this line?), and constructors, which create a new geometric object (what is the intersection point of these two lines?). Predicates usually make decisions based on the sign of an arithmetic expression—often a matrix determinant. Some geometric algorithms produce output that is purely combinatorial, such as a convex hull or an arrangement of hyperplanes, and rely exclusively on predicates. For example, a Delaunay triangulation can be computed using only orientation and incircle tests (which are discussed in the next section). Algorithms that use constructors are sometimes more difficult to make robust, because the objects they construct may take much greater numerical precision to represent than the input.

在几何算法中, 有两种类型的几何计算: 第一种断言(predicates), 即二支或三支决策(如一个点在一条边的左侧, 右侧, 还是在其上?), 第二种是构造(constructors), 即创建一个新的几何对象(两条直线的交点是什么?). 断言通常基于一个算术表达式的符号(通常是矩阵行列式)来做判断. 一些几何算法的输出结果是纯组合的, 如凸壳(convex hull)或者an arrangement of hyperplanes, 因此只用到断言计算. 另外, 计算Delaunay 三角化(triangulation)也只用到了定位(orientation)和圆内(incircle)检测(讨论见下章). 使用构造计算的算法有时更难做到稳健, 因为这些算法构造的几何对象需要比输入更好的数值精度来表示.

Geometric algorithms may be divided into several classes with varying amounts of robustness: exact algorithms, which are always correct; robust algorithms, which are always correct for some perturbation of the input; stable algorithms, for which the perturbation is small; quasi-robust algorithms, whose results might be geometrically inconsistent, but nevertheless satisfy some weakened consistency criterion; and fragile algorithms, which are not guaranteed to produce any usable output at all. The next several pages are devoted to a discussion of representative research in each class, and of the circumstances in which exact arithmetic and other techniques are or are not applicable. For more extensive surveys of geometric robustness, see Fortune [10] and Hoffmann [15].

几何算法可以根据稳健性被分成若干类: 精确算法(exact algorithms), 输出结果总是正确的;稳健算法(robust algorithms), 对输入的某些扰动总是正确的; 稳定算法(stable algorithm), 要求输入的扰动比较小; 拟稳健算法(quasi-robust algorithms), 它的结果在几何上可能不一致, 然而却满足某些弱一致性准则; 脆弱算法(fragile algorithms), 无法保证输出的结果是可用的. 下面几页主要讨论这几类算法中的代表性研究, 及精确的算法和其它技术在什么环境下是可用或不可用的. 更多几何稳健性的调研, 见文献 Fortune [9] 和 Hoffmann [15].

Exact algorithms. A geometric algorithm is exact if it is guaranteed to produce a correct result when given an exact input. (Of course, the input to a geometric algorithm may only be an approximation of some real-world configuration, but this difficulty is ignored here.) Exact algorithms use exact arithmetic in some form,
whether in the form of a multiprecision library or in a more disguised form.

精确算法. 如果一个几何算法给定精确的输入, 即可保证产生正确结果, 则称它是精确的. (当然, 几何算法的输入可能只是一些真实世界情况的逼近, 但是我们这里忽略这种困难). 精确的算法使用某种形式的精确算术运算, 如多精度软件包方式或更变相的方式.

There are several exact arithmetic schemes designed specifically for computational geometry; most are methods for exactly evaluating the sign of a determinant, and hence can be used to perform the orientation and incircle tests. These schemes are nearly always combined with a floating-point filter: each expression is first evaluated with ordinary floating-point arithmetic (roundoff error and all), and forward error analysis
is used to compute an upper bound on the error of the expression. If the error bound is smaller than the magnitude of the expression, then the sign of the expression is known to be correct. Exact arithmetic is used only if the error bound is too large.

有数种针对计算几何(computational geometry)专门设计的精确算术运算格式, 其中大部分格式是用来精确计算行列式(determinant)的符号的, 因此它们可以用来做定位和圆内检测. 这些格式几乎总是和浮点过滤器(floating-point filter)结合起来使用, 即每一个表达式首先用常规的浮点运算进行计算(存在舍入误差), 然后用向前的误差分析来确定该表达式计算误差的上限. 如果误差限比表达式的量级小, 这时算出的表达式的符号就是正确的. 如果误差限太大的话, 才用精确算术运算计算.