附件C：譯文
一個(gè)簡(jiǎn)單、高效的動(dòng)力學(xué)扳手(發(fā)明專利)

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

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

總括
算法式子 原理

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

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