二维域内分段直线路径计算复杂性的研究：基于图灵机的离散问题与多项式时间等价

2理论计算机科学电子笔记120（2005）45-57www.elsevier.com/locate/entcs关于二维域上求路的复杂性II：分段直线路Arthur W. 丑一克拉克大学数学与计算机科学系Worcester，MA 01610，USAKer-I Ko2计算机科学纽约州立大学石溪分校Stony Brook，NY11794摘要在基于图灵机的计算模型和离散复杂性理论中研究了在二维域中寻找具有常数线段数的分段直线路径的问题 证明了对于与多项式时间可计算距离函数相关联的多项式时间可识别域，该问题的复杂性等价于一个离散问题，该离散问题对于多项式时间层次的第二层CNOP是完备的.关键词：计算复杂度，分段直线路径，多项式时间层次，二维域1介绍在二维区域中寻找路径是计算复分析[7]、计算几何[5，6，12]和机器人学中的重要问题1电子邮件地址：achou@black.clarku.edu2电子邮件地址：keriko@cs.sunysb.edu1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.06.03346A.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）45C ∈ C[8]的一项建议。在Chou和Ko [2]中，我们研究了找到连接两个给定点并且完全位于给定二维域中的最短路径的计算复杂性。在本文中，我们继续这项调查研究的计算复杂性，寻找一个分段直线路径，连接两个给定的点与一个常数数量的直线段，完全位于一个给定的域（称为k-路径问题，如果在路径中的线段的数量被要求是最多k）。这个问题已经在计算几何[16]，机器人[14]和VLSI布局理论[15，17]的背景下进行了研究与Chou和Ko [2]一样，我们在可计算分析[13，18]和Ko和Friedman[11，9，10]的实函数复杂性理论的背景下研究k本研究的基本框架可总结如下（技术细节见第2节和[2]）：(1) 实值函数的基本计算模型是甲骨文图灵机，其实数输入以将整数映射到并元有理数的甲骨文函数的形式呈现。(2) 我们只考虑具有多项式时间表示的域。也就是说，如果给定的域S具有多项式时间表示，我们询问k(3) 我们考虑两类具有多项式时间表示的域：（A）具有多项式时间可计算边界曲线的有界单连通域;（B）具有多项式时间可计算距离函数的多项式时间可识别域(4) 解决k-路径问题的Oracle图灵机允许出错，只有当目标路径非常接近给定域S的边界时才会出错。在下文中，我们说关于域S的k-路问题（或最短路问题）对于某些离散复杂性类是C-困难的，如果每个问题B相对于域S的k路问题（或最短路问题）的解，可以在多项式时间内求解。基于这种硬度的概念，我们可以将Chou和Ko [2]的主要结果总结如下：(I) 如果一个域S满足上面定义的性质（A）或性质（B），那么相应的最短路径问题可以在多项式空间中用图灵机求解。(II) 存在满足性质（A）的区域S，使得相应的最短路问题是P-困难的.(III) 存在一个满足性质（B）的区域S，使得相应的最短路问题是PSPACE-困难的.A.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）4547112≥2122除了关于最短路问题的这些结果之外，Chou和Ko [2]还证明了关于1-路问题（在[2]中称为直线路问题(IV) 如果一个域S满足性质（A）或性质（B），则其核响应1-路径问题可由一个可解规划求解甲骨文图灵机(i.e.、1-路问题的补可由多项式时间非确定性Oracle图灵机求解关于k-路径问题的计算复杂性，本文证明了以下结果：(V) 存在一个满足性质（A）和（B）的区域S，使得相应的1-路问题是NP-困难的.(VI) 对于任意k≥2，如果整环S满足性质（A）或性质（B），则相应的k-路径问题可由一个可编程的Oracle Tur解决，机器（即，它可以通过多项式时间非确定性Oracle图灵机相对于NP中的Oracle集合来求解）。(VII) 对于任意k2 ，存在满足性质（B）的区域S，使得相应的k-路问题是CQP-困难的.由于基本符号和计算模型与[2]中使用的相似，因此我们将在第2节中仅给出计算k-路问题的形式模型读者可以参考[2]了解这个计算模型的动机和主要结果（V）-（VII）在第3节和第4节中给出。第五节讨论了k-路问题的一些悬而未决的问题.2k路问题的计算模型我们将在多项式时间层次的离散复杂性类的k-路径问题的计算复杂性的特点。这些复杂性类包括P、NP、NNP（coNP）、NNP。多项式时间层次中的集合具有简单的有界量化特征（参见，例如，Du和Ko [4]）。 特别地，一个集合A∈ {0， 1}在如果存在一个集合B∈P和一个多项式函数p，使得对于任何w∈ {0， 1}，长度为n，w∈ A（u，|u|= p（n））（λv，|v|= p（n））<$w，u，v<$∈ B.对于实函数的计算模型，我们遵循基于图灵机的实函数复杂性理论的基本方法（见[9，10]）。设D表示并元有理数的集合，即D ={m/2n：m∈Z，n∈ N}。Σ48A.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）45≥→≥ {∈}→⟨⟩对于任何n0，设D n=m/2 n：mZ .我们说一个函数φ：ND二进制收敛于实数x，或表示实数x，如果（i）对所有n ≥ 0，φ（n）∈ Dn，和（ii）对所有n ≥ 0，|x − φ（n）|≤ 2 −n。实函数计算的基本模型是oracle图灵机，它使用函数φ作为oracle，并将整数n >0作为输入。直观上，oracleφ表示实数x，输入n表示输出精度。定义2.1（a）函数f：R→ R被称为可计算的，如果存在一个oracle图灵机M，在一个oracle函数φ：N→ D上，该函数二进制收敛到实数x，输入n∈N，输出一个字符串d∈ Dn使得|d-f（x）|≤ 2 −n。(b)一个函数f：[0， 1]→ R是多项式时间可计算的，如果它是com-可由在多项式时间内操作的oracle图灵机M来计算（即， 对于任何预言函数φ，机器M总是在时间p（n）对某个多项式函数p）在输入n上上述定义可以自然地推广到二维平面上定义的函数。特别地，计算函数f：R 2→ R 2的图灵机使用两个表示R 2中的点z的预言机，并且它输出一对二进有理数d，e作为R 2中的输出点f（z）的近似。我们感兴趣的是以下二维平面R2上的寻路问题：k-P ATH P PROBLEM（k 1）：设S是二维平面R2中的固定区域。给定S中的两点x，y，判断在区域S中是否存在一条从x到y的至多由k条直线段组成的路径π(such路径被称为K段路径）。按照Chou和Ko [2]的方法，我们将研究关于具有以下类型的多项式时间表示的域S的这个问题：• 我们说S具有性质（A），如果S是有界的，单连通的（即，连通且无洞），并且其边界ΓS是多项式时间可计算的Jordan曲线（即，它是一对一的多项式时间可计算函数f：[0，1] R2的图像，除了f（0）= f（1））。• 我们说S具有性质（B），如果S是有界的、连通的、多项式时间可识别的，并且函数δS（x）是多项式时间可计算的。在上面，函数δS（x）表示点x∈R2与区域S的边界ΓS之间的欧几里得距离;即δS（x）=defnA.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）4549dist（x，r S）= min {|x-y|：y∈ Γ S}。 (In一般来说，对于两个闭集A，B，我们定义dist（A，B）= min {|x-y|：x∈A，y∈B}.）此外，一个集合S<$R2被称为多项式时间可识别的，如果存在一个预言图灵机M和一个多项式p，使得Mφ，<$（n）在时间p（n）计算域S的特征函数χS（z），只要（φ，<$）表示R2中的一个点z，其到S的边界ΓS的距离大于2−n;即，集合En（M）={z∈ R2：（<$（φ，<$）表示z）[Mφ，<$（n）/=χS（z）]}是{z∈R2：δS（z）≤2−n}的子集。有关多项式时间可识别集和距离函数的概念的更多讨论，请参见[1，2，3]。关于域的多项式时间可计算性的这些概念，我们关心的问题如下：假设域S具有性质（A）或性质（B）。域S的k路问题的复杂度是多少？类似于最短路径问题，如果我们将一个定义域S作为定义域S的特征函数fS，它将一对点x，y∈R2映射到{0， 1}（0表示否，1表示是），那么fS不是连续函数，因此是不可计算的（因为在可计算分析中众所周知，可计算的实值函数必须是连续的）。因此，计算的自然模型是允许计算函数fS的Oracle图灵机出错。下面的定义类似于[2]中给出的多项式时间可解最短路问题。定义2.2设k≥1。(a) 我们说关于区域S的k-路问题是可计算的，如果存在一个预言图灵机M，它使用四个预言机φx1，φx2，φy1，φy2表示两个点x，y∈S，并取一个整数n∈N作为输入，使得以下条件成立：(i) M总是停止并输出0或1。(ii) 如果在x和y之间的S中存在k-段路π，使得dist（π，ΓS）≥2−n，则M输出1。(iii) 若δS（x）≥2−n，δS（y）≥2−n，且S中不存在k-段路π在x和y之间，则M输出0。(b) 我们说关于域S的k-路问题是多项式时间可计算的，如果它是由上面（a）中描述的Oracle图灵机M计算的，满足以下额外条件：(iv) 有一个多项式函数p，使得对于任何预言机，输入上的Mn在p（n）步中停止。50A.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）45112−≥∈∈3上界我们首先考虑k= 1的情况关于1路问题的以下引理已在[2]中得到证明：引理3.1假设S具有性质（A）或性质（B）。然后，存在多项式时间非确定性预言图灵机M，使得对于分别表示两个点x，y ∈ S的任何给定预言机φ1，φ2，φ3，φ4，以及对于任何输入n∈ N，以下条件成立：(a) 如果线段xy位于S中且dist（xy，ΓS）≥2−n，则M不合格品。(b) 如果线段xy不在S中，则M接受。这个引理暗示了1路问题的上界。推论3.2假设S具有性质（A）或性质（B）。然后，1-区域S的路问题可由一个可积规划解Oracle图灵机（即，其补数可由多项式时间非确定性Oracle图灵机求解）。当k≥2时，我们可以证明k -路问题的上界.证明的思想是非确定性地猜测源点x和目标点y之间的k1个断点，然后应用引理3.1来验证由这些点形成的k段路径中的每个直线段位于域S中。我们省略了证明的细节定理3.3设k2和S具有性质（A）或性质（B）. 然后，存在多项式时间非确定性预言图灵机M和集合A NP，使得对于分别表示两个点x，y S的任何预言机φ1，φ2，φ3，φ4，以及对于任何输入n> 0，保持：(a) 如果存在从x到 y的k-段路π，使得π位于Domain中，S且dist（π，Γ S）≥ 2 −n，则M A，φ1，φ2，φ3，φ4（n）接受。(b) 如果不存在从x到 y的k段路径π，域S，则M A，φ1，φ2，φ3，φ4（n）拒绝。定理3.3中的预言图灵机M可以修改为图灵转换器M1，只要M接受，它就输出k段路径推论3.4设k≥ 2且S具有性质（A）或性质（B）。然后，存在多项式时间非确定性预言图灵转换器M1和集合A ∈ NP，使得对于分别表示两个点x，y∈S的任何预言机φ1，φ2，φ3，φ4，以及对于任何输入n> 0，满足以下条件A.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）455111≥1∈⊆≥≥22⊆22保持：(a) 如果存在一条从x到y的k段路π，使得π位于定义域S中，并且dist（π，ΓS）≥ 2 −n，则M A ，φ1，φ2， φ3，φ4（n）接受并输出k− 1个并矢点x1，x2，. ，xk−1使得由xx1，x1x2，.，xk−2xk−1，且xk−1y在S中。(b) 如果不存在位于区域S中的从x到y的k段路π，则M A，φ1，φ2，φ3，φ4（n）拒绝。4下界我们首先考虑1路问题。下面定理的证明类似于定理4.3的证明，但比定理4.3的证明简单（对于k2的情况）。 我们省略细节。定理4.1对任意集合A ∈ P，存在满足性质（A）和（B）的域S[0，1]2，使得A相对于域S的1-路问题的解是多项式时间可计算的。与推论3.2一起，我们得到了1-路问题复杂性的以下特征。推论4.2下列等式是等价的：(a) P= NP。(b) 对于任何满足性质（A）或（B）的区域S∈ [0，1]2，相应的1-路问题是多项式时间可计算的.接下来，我们考虑k-路问题，2. 我们证明，对于每一个k2，则存在满足性质（B）的区域S，使得区域S的k-路问题是KNP-困难的.定理4.3设k≥2.对任意集合A ∈ P，存在一个整环S[0，1]满足性质（B）使得A相对于域S的k-路问题的解是多项式时间可计算的。证据 （草图）。 我们首先考虑k= 3的情况。回想一下，A∈P意味着存在一个集合B∈P和一个多项式函数p使得，对于任何长度为n的w∈ {0， 1}n，w∈ A（u，|u|= p（n））（λv，|v|= p（n））<$w，u，v<$∈ B.对于任何长度n>0的w∈ { 0， 1}n，我们将定义一个域Twn[0，1]2。对于任意k，0≤k≤ 2p（n）− 1，我们令uk是{0， 1}n中的第k个字符串;即，52A.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）45| |⟨ ⟩ ⟨ ⟩ ⟨⟩⟨ −⟩⟨ −⟩≤ ≤−uk是整数k的p（n）位二进制表示，可能有前导零。我们还令ak=k·2−p（n），对任意0≤k≤ 2p（n）。现在，对于每个w∈ {0， 1}n和每个j，0≤j≤2p（n）− 1，其中n=w，我们定义一个函数f w，j将单位区间[0，1]映射到[0，1]中的曲线2。我们将中间值[0， 1]in定义为 2p （ n ）个子中间值[ak ， ak+1]，其中k=0，1， . . ，2p（n）−1，函数fw，j将每个hiterval[ak，ak+1]映射到一个线段或由两个线段组成的曲线。也就是说，对于每个k，0 ≤k≤2 p（n）−1，(i) fw，j将s[ak，ak+1]映射到两个端点都是1/4+的直线上ak/2，aj和 1/4 +ak+1/ 2，aj， ifw，uj，uk∈B;and(ii) fw ， j 将 s[ak ， ak+1] 映 射 到 一 个 2-s 段 tpathfrom1/4+ak/2 ， aj 到1/4+ak+1/2，aj，其中中间有一个断点point1/4+ak/2+2−p（n）−2，aj+2 −p（n）−1，如果kw，u j，uk/∈ B.设Γw，j表示fw，j在[0，1]上的像。在图1中，我们显示了曲线Γ w，j，其中p（|W|）= 3，j= 0，并且对于k= 0，3，4，5，7，对于k=1，2，6，（在图1中，ak表示s1/4 +ak。）.........（1/4，0）（a1*，0）（a2*，0）（a3*，0）Fig. 1. 曲线Γw，j.（a6*，0）（a7*，0）（3/4，0）接下来，对于每个w∈ {0，1}n和每个j，0≤j≤2 p（n），其中n=|W|，我们定义一个闭集X w，j。首先，设R w，j，0为四个角为<$1/8，a j−1+2 −p（n）−2<$，<$1/4，a j−1+ 2 −p（n）−2<$，<$1/4，a j<$and<$1/8，aj<$的矩形;设R w，j，1为四个角为<$3/4，a j−1+ 2 −p（n）−2<$，7/8，aj−1+ 2 −p（n）−2，7/8，a jand 3/4，a j的矩形。现在，集合X w，j可以定义如下：(i) 对于j=0，Xw，0是包围在线1，0，0，3，0，和4 4曲线rw，0.(ii) 对于1j2名p（n）1，Xw，j是矩形Rw，j，0，Rw，j，1的并集以及1/4，a j2 −p（n）−2到3/4，aj2−p（n）−2和rw，j之间的区域。(iii) 对于j= 2 p（n），X w，j是三个矩形的并集：R w，j，0，R w，j，1，以及四个角为，，和的矩形。我们还定义Y w为两个矩形的并集，它们的四个角分别为：<$7/8，1− 3·2 −p （ n ） −2<$ ， <$15/16 ， 1 − 3·2 −p （ n ） −2<$ ， <$15/16 ， 1 <$ ，<$7/8，1 <$和<$15/16，2 −p（n）−2<$，<$1，2 −p（n）−2<$，<$1，1 <$，<$15/16，1 <$。最后，我们让A.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）4553YwXw，m-1Xw，m-2...Xw，2x宽X w，1y.WXw，mj=0⟨⟩⟨ −⟩p（n）-∈WXw，0图 二、 当m=2p（n）时，定义了T w的定义.T=[0，1]2−2p（n）X w，j-Yw，xw=1/ 8− 2−p（n）−2，2−p（n）−1，yw=<$7/8 + 2 − p（n）− 2，2 − p（n）− 1 <$（见图2）。我们观察到域Tw和点xw，yw满足以下性质：(1) 如果存在一个整数j，0≤j≤2p（n）−1，使得对所有k，0≤k≤21，w，uj，ukB，则在T w中有一条从xw到yw的三段路，其中间两个断点是1/82 −p（n）−2，a j+ 2 −p（n）−3和7/8+ 2−p（n）−2，aj+ 2−p（n）−3。(2) 否则，所有2个p（n）可能的路径都被函数fw，j的一些凸块阻塞，因此在Tw中不存在从xw到yw的3段路径。现在，我们可以将域Tw组合成一个域S。对于每个n>0，设cn= 1− 2−（n−1）。我们定义，对于每个长度为n的w∈ {0， 1}，域Sw是域Tw在线性变换下的像，gw（nx1，x2n）=ncn+x1·2−n，（kw+x2）·2−n，其中kw是其n位二进制表示（可能有前导零）正好是w的整数。 设S=w∈{0，1}+Sw，（见图3）。证明S满足性质（B）并不难也就是说，对于任何给定的点z∈ [0，1]2且整数n> 0，如果dist（z，Γ S）≥ 2 −n，则我们可以确定z是否∈S并找到一个并矢有理d，使得|d− dist（z，Γ S）|≤ 2 −n。此外，从上述关于Tw和xw，yw的观察（1）和（2），54A.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）45⊆...yw.X.WS10S100S011第一S010S0S001S00S000图三. 域S.见图4。 在k= 8的情况下，域Tw。我们看到w∈A当且仅当在gw（xw）和gw（yw）之间存在一条三段路因此，w∈A的问题可以在多项式时间内通过询问S中是否存在从 gw（xw）到gw（yw）的三段路来解决这就完成了k= 3的情况的证明。对于k >3和k= 2，我们可以修改上述构造以得到所需的域S。我们省略了细节，仅在图4中示出了k= 8的情况下的域Tw，在图4中示出了k= 2的情况下的域Tw。5.H推论4.4设k≥ 2。以下是等价的：(a) P=2 1(b) 对于任何满足性质（B）的域S [0，1]2，k路问题是非确定性多项式时间可计算的。我们注意到，在离散复杂性理论中已知P=NPA.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）45551⊆≥∈.. yWX.W图五. 在k= 2的情况下，域Tw意味着P=P=P（参见，例如，Du和Ko [4]）。因此，推论4.2也2 1对于k≥2的k-路问题成立.推论4.5设k≥ 2。以下是等价的：(a) P= NP。(b) 对于任何满足性质（B）的域S∈[0，1]2，k路问题是多项式时间可计算的。5最后发言我们观察到定理4.3中构造的域S虽然满足性质（B），但不是单连通域。事实上，它包含无限数量的孔。这个构造是否可以被加强以使S成为单连通域或多连通域（即，一个有有限个洞的域），是一个有趣的开放问题。我们知道定理4.1的结果也适用于k >1的k-路问题.因此，对于满足性质（A）或性质（B）的单连通域S，我们有以下较弱的下界推论5.1设k2.对任意集合A ∈ P，存在满足性质（A）和（B）的单连通域S[0，1]2，使得A相对于域S的k-路问题的解是多项式时间可计算的.另外，我们还观察到定理中构造的域S中的洞如果我们考虑三维域，则可以消除4.3。56A.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）452推论5.2设k≥2。对任意集合A∈ P，存在满足性质（A）和（B）的单连通三维区域S<$[0，1]3，使得A相对于区域S的k-路问题的解是多项式时间可计算的.证明的草图。我们描述的情况下k=3的想法。考虑定理4.3中定义域Tw的构造。我们可以把Tw看作单位正方形[0， 1]2，其中孔数为Xw，j，0≤j≤ 2p（n），且Yw。现在，我们从单位立方体[0， 1]3开始，对于每个j，0≤j≤ 2p（n），我们挖一个形状为Xw，j深度为1/ 2的洞（从顶部开始），以及一个形状为Yw深度相同的洞。将剩下的区域称为Uw（包含底部立方体的一半，所以是简单连接的）。 此外，还应附上两个酒吧B w，1=[0，1/8] × [− 1，0] × [7/8，1]，B w，2=[7/8，1] × [− 1，0] × [7/8，1]至U w。LetTwJ是UwBw、1Bw、2和LetxwJ的整数倍 =0.1/16，−15/16，15/16yw=15/16，−15/ 16， 15/ 16<$（因此xw和yw接近于两个条Bw，1和Bw，2）。 我们注意到，从xJw到ywJ mustcontinalineesgmmBw，1toUw，anddataline段从Uw到Bw，2，因此唯一可能的3段路径从xJw到ywJ 我在国内的上半部分都很活跃，而且我也很喜欢这种情况。(1)（2）定理4.3的证明。有了这样的能力，我们就可以在两个星期内 i n到一个单一的domainS J它是单连通的，满足性质（B）。实际上，SJ也满足性质（A），因为可以计算原始域Tw中的每个孔Xw，j在多项式时间内 ，|W|.Q引用[1] Chou ，中国古猿A. W. 和 Ko ， K. ，二维区域的计算复杂性， SIAM J. COMPUT 。24（1995），923[2] Chou，中国古猿A. W. 和Ko，K.， 关于在一个 二维域I：最短路径，Math. Logic Quarterly，待 发 表 ; 也 可 参 见 Proc. International Conference on Computability and Complexity inAnalysis ，2003，Informatik Berichte 302- 8/2003 ，FernUniversitaütinHage n，Hage n，Germany。[3] Chou，中国古猿A. W.和Ko，K.，关于二维域的距离函数复杂性的注记。[4] 杜，D.- Z.和Ko，K.，计算复杂性理论，约翰·威利父子公司，纽约，2000年。[5] 吉巴斯湖Hershberger，J.， Leven，D.， Sharir，M. Tarjan，R.， 简单多边形内可见性和最短路径问题的线性时间算法，第二届ACM计算几何研讨会论文集，ACM，纽约，1986年，第100页。1-13号。[6] 吉巴斯湖和Hershberger，J.，最优最短路径查询在一个简单的多边形，第三届ACM计算几何研讨会论文集，ACM，纽约，1987年，页。50比63[7] Henrici，P.，应用与计算复分析，第1-3卷。约翰威利父子，纽约，1974年，1977年，1986年。A.W. Chou，K.-I. Ko/Electronic Notes in Theoretical Computer Science 120（2005）4557[8] 霍普克罗夫特，J.E.，Schwartz，J. T.和Sharir，M.，机器人运动的规划、几何和复杂性，Ablex，Norwood，NJ，1987。[9] 好，好。，ComplexityTheoryofRealFunctions，Birkh？auser，Boston，1991.[10] Ko，K.，多项式时间可计算性分析，在递归数学手册，卷。2：递归代数，分析和组合，余。L. Ershov等人，编辑，Studies in Logic and the Foundations of Mathematics，Vol. 139，Elsevier，Amsterdam，1998，pp.1271[11] 科，K.Friedman，H.，实函数的计算复杂性理论Comput. Sci.20（1982），323-352.[12] Mitchell，J.和Sharir，M.，最短路径在三维空间中的新结果，Proc.20th ACM Symposium onComputational Geometry，ACM，NY，2004（即将出版）。[13] Pour-El，M.和理查兹，我，《分析与物理中的可计算性》，Springer-Verlag，柏林，1989年。[14] Reif，J.H.和Storer，J.A.，最小化在多边形内部离散移动的转弯IEEE J.机器人自动，3（1987），182[15] Storer，J.A.， 关于最小节点成本平面嵌入，网络14（1984），181[16] Suri，S.，提出了一种求解简单多边形最小连接路径的线性时间算法。Vision，Graphics，ImageProc.35（1986），99-110.[17] 塔马西亚河，关于在网格中嵌入具有最小弯曲数的图，SIAM J. COMPUT。16（1987）421-444。[18] Weihrauch，K.，可计算分析，Springer-Verlag，海德堡，2000年。