一个简单、高效的动力学扳手(发明专利)[外文翻译].doc

附件C：译文
一个简单、高效的动力学扳手(发明专利)

摘要
我们提出一种新的简单的（1+ε）扳手，它的大小是Ｏ(n/ε2)，由一些列在平面上的n个点组成，当这些点移动时，这些状态能够被有效地维持。假设这些点的轨迹能用多项式描述，他们的角度大多数是s，对于这个扳手它的数目的拓扑变化是Ｏ((n/ε2)•λs+2(n))，在每一个结果中，扳手可以升级【1】一次。

类别、学科描述符
F.2.2【算法和问题复杂性的分析】：非数字算法和问题——几何问题和算法指令

总括
算法式子 原理

关键字
几何扳手 动力学数据结构

1. 简介
几何网络在空间d的n个点的系列P中，它是一个带有定点P的无方向性加权图G(P,E)，它的边是直线型的线段，将成对的点连接在P。几何网络边缘（p，q）的重量等于p和q之间的距离。通常所考虑的空间是欧几里德平面，但是也可以考虑其他的度量和/或更高的维度。许多真实的自然模型几何网络，例如道路网络，通讯网络等等。当为给定的点系P设计网络时，可以考虑一些标准。特殊情况下，在许多应用场合，确保每个成对点在P处的快速连接是很重要的。由于这个原因在每一个成对点之间有个直接的联系是很理想的——网络将是一个完整的图——但是在大多数的应用中，由于成本高，是不可接受的。这个就产生了扳手的概念，下面所定义的。
对于一个几何图形G(P,E)和两个点p，q∈P，我们用d G(p,q)表示它们在图中的距离，也就是说，它们中（加权）最短路径的长度。我们认为如果d G(p,q)≤t•|pq|，而且所有的成对的点p，q∈P，那么G对于P来说是一个（几何的）t型扳手，此时|pq|表示pq部分的长度。G的扩张或伸长系数是最小值t，因此G是一个t型扳手。自从Chew【3】，Peleg和Ullman【18】在后来的论文中的介绍，扳手被定义在一个更一般的理论图线环境中——大约二十年前，人们对扳手进行了广泛的研究，写了许多关于这个题目的论文，包括一些调查【8，11，20】，而且就在最近一本仅仅关于几何扳手的书出版了【17】。