附件C：譯文
一個簡單、高效的動力學扳手(發(fā)明專利)

摘要
我們提出一種新的簡單的（1+ε）扳手，它的大小是Ｏ(n/ε2)，由一些列在平面上的n個點組成，當這些點移動時，這些狀態(tài)能夠被有效地維持。假設這些點的軌跡能用多項式描述，他們的角度大多數(shù)是s，對于這個扳手它的數(shù)目的拓撲變化是Ｏ((n/ε2)•λs+2(n))，在每一個結(jié)果中，扳手可以升級【1】一次。

類別、學科描述符
F.2.2【算法和問題復雜性的分析】：非數(shù)字算法和問題——幾何問題和算法指令

總括
算法式子 原理

關(guān)鍵字
幾何扳手 動力學數(shù)據(jù)結(jié)構(gòu)

1. 簡介
幾何網(wǎng)絡在空間d的n個點的系列P中，它是一個帶有定點P的無方向性加權(quán)圖G(P,E)，它的邊是直線型的線段，將成對的點連接在P。幾何網(wǎng)絡邊緣（p，q）的重量等于p和q之間的距離。通常所考慮的空間是歐幾里德平面，但是也可以考慮其他的度量和/或更高的維度。許多真實的自然模型幾何網(wǎng)絡，例如道路網(wǎng)絡，通訊網(wǎng)絡等等。當為給定的點系P設計網(wǎng)絡時，可以考慮一些標準。特殊情況下，在許多應用場合，確保每個成對點在P處的快速連接是很重要的。由于這個原因在每一個成對點之間有個直接的聯(lián)系是很理想的——網(wǎng)絡將是一個完整的圖——但是在大多數(shù)的應用中，由于成本高，是不可接受的。這個就產(chǎn)生了扳手的概念，下面所定義的。
對于一個幾何圖形G(P,E)和兩個點p，q∈P，我們用d G(p,q)表示它們在圖中的距離，也就是說，它們中（加權(quán)）最短路徑的長度。我們認為如果d G(p,q)≤t•|pq|，而且所有的成對的點p，q∈P，那么G對于P來說是一個（幾何的）t型扳手，此時|pq|表示pq部分的長度。G的擴張或伸長系數(shù)是最小值t，因此G是一個t型扳手。自從Chew【3】，Peleg和Ullman【18】在后來的論文中的介紹，扳手被定義在一個更一般的理論圖線環(huán)境中——大約二十年前，人們對扳手進行了廣泛的研究，寫了許多關(guān)于這個題目的論文，包括一些調(diào)查【8，11，20】，而且就在最近一本僅僅關(guān)于幾何扳手的書出版了【17】。