本 书叙述的内容不属于欧几里得的几何证明公理化范畴，而是属于欧几里得的几何构造 ，即由算法和复杂性分析所组成。欧几里得的几何构造满足算法的所有要求： 无二义性、有 穷性、确定性、能行性、输入、输出、正确性等。在欧几里得的几何构造中，限定了可允许 使用的工具(直尺和圆规)及原始运算(圆规的一个脚置于一个给定点或一条直线上； 作一个 圆； 直尺的边通过一个给定点； 作一条直线)。但欧几里得原始运算并不能胜任所有的几何 计算(如角的三等分)，这一点直到19世纪，阿贝尔、伽罗华等数学家才给出了证明。 在一个几何构造过程中，执行原始运算的总次数称为该过程的复杂性度量，这个概念对应于 算法的时间复杂度。同样地，还有对应于算法的空间复杂度的概念。这是欧几里得几何构造过 程复杂性的定量测度。 称为计算几何的学科大致有下述几种： Forrest等人依据样条函数处理曲线和曲面(实际上更 接近于数值分析)； Minsky和Papert写的一本名为《感知机》的书(副标题为“计算几何”) ，该书陈述用简单回路构成的网络实现模式识别的可能性(应属于人工神经网络)； 计算机图 形学是研究用计算机进行图形信息处理(包括表示、输入、输出、存储、显示、检索与变换 等)和图形运算(如图的并、交运算)的一门学科，而不是算法分析； 几何定理的机器证明， 主要研究定理证明的探索方法及证明过程的推断，而不是几何本身。本书讨论的内容与上述计算几何学 科所研究的内容不同，是属于Shamos的文章(1975a)中命名的“计算几何”。为了不 与上述“计算几何”的命名混淆，并突出Shamos的计算几何是研究几何问题的算法及复杂性 的，故本书中将Shamos的计算几何称为S计算几何，而书名仍称为计算几何。 欧几里得货郎担问题、最小生成树问题、隐藏线(面)问题和线性规划问题等许多问题是S计 算几何研究的基本问题。在19世纪的文献中，已经出现了对这些问题的算法研究，但对几何 问题进行几何算法的系统研究还是近20多年的事情。 第0章预备知识 计算几何——算法设计与分析 本书将通过对几何问题的研究，在以下各章节中给出S计算几何的观点、研究方法与几种重 要的几何结构。S计算几何的一个基本观点是，经典的几何对象的表征常常不适合于有效算 法的设计。因此有必要建立一些概念及相关的性质，以适应于有效算法的设计。 本章将介绍有关算法与数据结构的一些知识、几何知识及计算模型。这些内容是以后章节所 需要的。 0.1算法与数据结构 0.1.1算法 众所周知，算法是求解一个问题类的无二义性的有穷过程。这里的过程是指求解问题执行的 一步一步动作的集合，每一步动作只需要有限的存储单元和有限的操作时间。另外，如果详 细说明一台典型的计算机以及与这种计算机通信的语言，那么凡用这种语言编写的、可以在 给定的计算机上执行的过程便称为算法。随机存取机器(RAM)、图灵机等可以作为典型的计 算机，拟ALGOL语言作为描述算法而非执行的语言。应该指出，算法不等于程序，因此描述 算法的方式将是多种形式的，如在拟ALGOL语言的描述中可以使用数学记号和自然语言。 为了把算法转换成上机程序，还需要进行编程工作。 算法的复杂性包括算法的时间复杂性和算法的空间复杂性。为了说明复杂性的概念，先介绍 问题规模的概念。用一个与问题相关的整数量来衡量问题的大小，该整数量表示输入数据量 的尺度，称为问题的规模。比如，行列式的规模可以用其阶数n来表示，图问题的规模可以用其边数或顶点数来表示，等等。 利用某算法处理一个问题规模为n的输入所需要的时间，称为该算法的时间复杂性。它显 然是n的函数，记为T(n)。 类似地，可以定义算法的空间复杂性S(n)。 下面主要讨论算法的时间复杂性。由于一般不需要知道精确的时间耗费，只要知道时间耗费 的增长率大体在什么范围内即可，因此我们引入算法复杂性阶的概念。 如果对某一正常数c，一个算法在时间cn2内能处理规模为n的输入，则称此算法的时间复 杂性是O(n2)，读作“n2阶”。一般定义如下： 如果存在正常数c和n0，使得当n≥n0时有T(n)≤cf(n)，则称T(n)是O(f(n))，记作T(n) =O(f(n))。此时，f(n)是T(n)的增长率的一个上界。 如果T(n)=O(f(n))和f(n)=O(T(n))同时成立，则称T(n)是θ(f(n))，记作T(n)=θ(f(n) )。此时，T(n)和f(n)的增长率是同阶的。 如果存在正常数c，使得对无穷多个n关系式T(n)≥cf(n)成立，则称T(n)是Ω(f(n))， 记作T(n)=Ω(f(n))。此时，f(n)是T(n)的增长率的一个下界。 如果T(n)=O(f(n))和T(n)=Ω(f(n))同时成立，则有T(n)=θ(f(n))。 根据上述定义，两个函数如果同阶，那么它们可以相差一个常数因子，还可以相差比阶低的 项，即函数中的低阶项并不影响它的阶数。这时，若要进一步分析T(n)，就应考虑常数因子 和低阶项对T(n)的影响。 一般情况下，都是取一个简单形式的函数作为阶数的规范表示，如n2，n3，n6等。实 用中也是这样处理的。 一个算法的时间复杂性如果是O(2n)，则称此算法需要指数时间。而时间复杂性如果是O(n k)(k为有理数)，则称此算法需要多项式时间。当n很大时，指数时间和多项式时间存在 很大的差别。以多项式时间为限界的算法称为有效算法。有效算法的一个本质特征是可以按 常规的方法在较短的时间内用一个确定的计算装置进行机械的计算。该计算装置的典型模型 是图灵机和RAM(random access machine)机。 算法的时间复杂性分为最坏情况的时间复杂性和平均情况的时间复杂性。对于给定规模为 n的各种输入，某算法执行每条指令所需要的时间之和的最大值，称为该算法的最坏情况的 时间复杂性； 对于给定规模为n的各种输入，执行每条指令所需要的时间之和的平均值，称 为平均情况的时间复杂性(或期望复杂性或平均特性)。由于规模为n的“输入”出现的概 率不同，所以有时要考虑加权平均特性。 为了求平均特性，必须对输入量的分布作某种假设。然而切合实际情况的假设，在数学上往 往不易处理。因此，确定平均特性比确定最坏情况的时间复杂性要难。 在最坏情况的时间复杂性和平均特性的定义中，都提到“指令”。由于不同的机器执行某一 指令(如加法指令)所需要的时间可能不同，因此同一算法在不同机器上执行时所需要的时间也 可能不同。为了消除这一差距，人们引入一个理想的计算模型，用它代替具体的机器，以建 立时空复杂性概念。这个理想的计算模型称为随机存取机器(RAM)，它只有一个累加器，而 且不允许自行修改指令。 RAM机器由一条只读输入带、一条只写输出带、一个程序存储器、一个存储器和指令计 数器组成，如图0-1所示。 图0-1RAM机器 输入带被划分为一系列方格，每个方格可以放一个整数。每当从输入带读出一个符号时，带 头向右移动一格。输出带也被划分为一系列方格。执行一条写指令时，在输出带当前处于带 头下的方格里打印一个整数，且带头右移一格，带头不能改写已印出的整数。 存储器由一系列寄存器r0，r1，r2，…组成，每个寄存器能放下一个任意大小的 整数。寄存器ri的个数不受限定。 RAM的程序不存放在存储器里，于是可假设程序不能修改自身。程序是带(也可不带)标号的 指令序列，指令与实际的计算机一样，有算术指令、输入输出指令、间接寻址和转移指令等 。用这些指令编写的程序称为RAM程序。RAM的所有计算都在第一个寄存器r0(称为累 加器)中进行。r0中也可放一个任意大小的整数。 RAM程序的最坏情况时间复杂性和平均特性的定义与上面相同。 下面介绍最佳算法的概念。 在解决某一问题P的一类算法A中，需要操作次数最少的算法称为求解 问题P算法类A的最佳算法。这里是用指定基本操作来确定算法类的。而算 法A的基本操作是指A的关键操作，并且A的操作总数与基本操作次数成正比(当n增加时)。 形式上，设算法类A求解问题P。对任一A∈A，其时间复 杂性为TA(n)，定义 CP(n)=minA∈A｛TA(n)｝ 称为问题P关于A的计算复杂性。问题P的计算复杂性是P所固有的。由于A 是A中任一算法，所以CP(n)难以估计。为此可以对问题P先求出在算法 类A下CP(n)的下界(称为下界问题)，然后努力寻找达到这一计算复杂度 的算法。 若能构造函数g(n)，并可以证明，对任一A∈A，有TA(n)≥g(n)成立， 则g(n)是CP(n)的一个下界。 设已找到求解P的算法A，A∈A，并分析A的复杂性TA(n)，有 CP(n)≤TA(n)=f(n) 则f(n)是CP(n)的一个上界。 设f(n)，g(n)分别为CP(n)的上界和下界，如果f(n)=θ(g(n))，而且f(n)=TA(n)，则A 是A中求解问题P的最佳算法(复杂性的阶不可能降低，但系数可能减少)。 如果f(n)≠θ(g(n))，则存在优于A的算法或者存在一个更低的下界。 设A是求解问题P的算法，那么可以用执行A时的“循环次数”作为算法时间复杂性的度量标 准； 在定义“最坏情况时间复杂性和平均特性”时，可考虑将“执行每条指令所需要的时间 之和”作为度量标准； 另外，“基本操作的次数”也可作为度量标准。前者使用方便，但估 计粗糙； 中者与机器的类型有关，需要引入一个抽象的计算模型，它对建立“最坏情况时间 复杂性和平均特性”的概念有益； 后者与机器、所采用的语言、实现方式等均无关，是较理 想的度量 标准。值得注意的是，我们只在同一种度量标准下比较某类算法中不同算法的优劣，而且在 比较阶的同时，要特别注意以何种运算作为时间单位。如果时间单位不同，那么同一算法可 能有不同的阶。 本书的主要目的是阐述求解几何问题的算法，以及对算法最坏情况复杂性的估计。 算法设计中的常用方法也适用于几何算法设计，如分治法、贪心法、递归法、随机化方法 和动态规划方法等。除了这些方法之外，依据几何问题的特征，将采用一些特殊的技巧， 如累接、修剪和搜索、几何变换、轨迹和扫描等。下面简要介绍平面扫描方法，其他方 法将在后续章节中结合具体问题予以介绍。 给定平面上n条线段的集合S，报告线段集合中的所有交点。考虑垂直直线l，它将平面分割 成两个半平面，即左半平面L和右半平面R。显然，问题的解是L中的解和R中的解的并。当直 线l穿过线段集合S时必与某些线段相交。另外，容易观察到，当l非常接近某两条线段的交点时，该两条线段和l的两个交点在l上是相邻的。因此，只要对S生成所有的垂直切割，就可以发现所有的交点。这就相当于把直线l从左向右扫过平面，故称为平面扫描方法。当然，不可能连续地生成所有垂直切割 的无限集合，但可以通过把平面划分为若干个垂直长条来实现，这些垂直长条由S中线段端 点或交点确定。因此，只需从垂直长条的左边界跳到右边界，修改长条的次序，并测试l上 新的相邻线段是否相交。l从左向右扫过平面时，在称为“事件点”的特殊点处暂停，以 测试S中某些线段对是否相交。为此，需要两个基本结构： (1)事件点进度表。S中线段端点 的x坐标的排序，它确定了扫描线l的暂停位置。执行平面扫描算法过程中，发现交点时便要 修改事件点进度表。(2)扫描线状态，它是扫描线l和S中线段的交点的一种描述。在每个事 件点处修改扫描线状态。 0.1.2数据结构 数据结构是组织信息的方式，它和算法一起使问题可能得到有效的解。下面简要回顾有 关的数据结构及其功能。 几何算法设计中遇到的对象是集合和序列。设U是某种几何对象的全集，u是U中的任意元 素，而S是U的子集。集合操作中的基本运算有： (1)MEMBER(u,S)： u∈S？ (2)INSER T(u,S)： 把u加入S； (3)DELETE(u,S)： 从S中删去u。设｛S1，S2，…，Sk｝ 是一组两两不相交的集合，其上的运算有： (1)FIND(u)： 若u∈Si，则报告i； (2 )UNION (Si,Sj； Sk)： 产生Si和Sj的并，且记为Sk。当U是全序时，有运 算： (1)MIN(S)： 报告S的最小元素； (2)SPLIT(u,S)： 把S划分为S1和S2，且S 1=｛v|v∈S并且v≤u｝,S2=S-S1； (3)CONCATENATE(S1，S2)： 设对于任意a ∈S1和b∈S2，有a≤b，产生有序集S=S1∪S2。 对于有序集，依据支持的运算分类数据结构如下： 字典，支持运算MEMBER，INSERT，DELETE ； 优先队列，支持MIN，INSERT，DELETE； 可并队列，支持INSERT，DELETE，SPLIT，CONCAT ENATE。通常以均衡二叉树来实现上述数据结构，此时，完成INSERT等运算的时间和存储在 数据结构中元素个数的对数成比例； 存储和集合大小成比例。另外，上述数据结构还可以 表示为一个线性的元素组(称为表)，根据插入和删除的位置不同而分为队和堆栈，以U1 表示队或堆栈。记号“U1”表示插入U1，而“U1”表示从U1中删去。 通过对无序集元素采用赋予“名字”，且用字母次序的办法可以把无序集转变成有序集，这 种情况的一种数据结构是可归并堆栈，它支持INSERT，DELETE，FIND，UNION等运算。仍以 均衡树来实现该数据结构，并且耗费时间O(logn)完成INSERT等运算，其中n是 存储在可归并堆栈中集合的大小。如无特别说明，本书中出现的logn均是以2为底的对数函 数。 几何算法设计中广泛使用上述数据结构，此外，依据几何问题的特征，我们还采用线段树和 双重连接边表等特殊的数据结构。 1. 线段树 线段树是一棵二叉树，记为T(a,b)，并用v表示它的根，其中参数a,b是两个整数，它们表示 一个区间的始点和终点，记为B［v］=a,E［v］=b。线段树T(a,b)可以递归地构造如下： 它 包含一个根v，根具有参数a和b，且若b-a＞1，则它有左子树T(a, (B［v］+E［v］)/2)和右子树T((B［v］+E［v］)/2，b)，其中“”表示低限。左、右子树的根分别为LSON［v］和RSON［v］。结点v所代表的区间由B［v］和E［v］确定，并满足关系式［B［v］，E［v］］［a,b］。图0-2表示线段树T(2，14)。线段树的叶结点所代表的区间，称 为基本区间，而其他结点表示［B［v］，E［v］］=［a,b］中的某个子区间。容易将T(a,b) 建成均衡树(所有叶结点位于相邻的两极上)且具有深度 log(b-a) ，其中“ ”表示高限。 线段树支持插入和删除运算。给定线段树T(a,b)和任意区间［c,d］，下述过程将［c,d］插 入线段树T(a,b)。 图0-2线段树T(2，14) procedure INSERT(c,d； v) begin ifc≤B［v］ ∧ E［v］≤dthen把［c,d］ 分配给v elseifc＜(B［v］+E［v］)/2thenINSERT(c,d； LSON［v］)； if(B［v］+E［v］)/2 ＜dthenINSERT (c,d； RSON［v］) end INSERT(c,d； root(T))运算在T中沿下述路径进行： 从根到结点(称为树杈)v的初 始路径，称为PIN； 从v引出两条路径PL和PR。或者把整个［c,d］分配给v (此时，PL和PR均为空)； 或者整个分配给PL结点的所有右子结点(这些右子结点不 在PL上)，以及PR结点的所有左子结点(这些左子结点不在PR上)，确定［c,d］的分配 结点。如图0-3所示，其中双圆圈结点是分配结点。 图0-3把区间［62，87］插入T(1，213) 通常只需要知道分配给结点v的区间集合的基数，用c［v］表示该基数，然后若将［c,d ］再分配给v，则有 c［v］←c［v］+1 DELETE(c,d； v)运算表示如下： procedure DELETE(c,d； v) begin ifc≤B［v］ ∧ E［v］≤dthenc［v］←c ［v］-1 elseifc＜ (B［v］+E［v］)/2 then DELETE(c,d； LSON［v］)； if (B［v］+E［v］)/2 ＜dthenDELETE(c,d； RSON［v］) end 线段树是一种常用的数据结构。若要知道包含给定点x的区间个数，则对线段树T进行一次 二叉查找(即从根到一个叶的一条路径的遍历)即可解决问题。 2. 双重连接边表 双重连接边表是另一种常用的数据结构，它适合于表示嵌入平面的平面图(连通)。给定平面 图G=(V，E)，G的平面嵌入是将V中的顶点映射到平面中的一点，且E中的边映射到边的端点 的两个像之间的一条简单曲线，所有简单曲线除端点外互不相交。可以取简单曲线为直线段 。 设平面图G=(V,E)的顶点集V={v1，v2,…，vn}，边集E={e1，e2,…，em}。G的双重连接边 表如图0-4所示。每条边ei给4个信息段V1，V2，F1和F2及两个指示字段P1和P 2，所以可以用相同名字的6个数组实现对应的数据结构，每个数组包含m个单元。各信息 段的意义如下： V1与V2分别为边ei的起点和终点； F1，F2分别表示位于有向边e i的左侧面和右侧面的名字； 指示字P1(P2)指向一条边及端点，该边是边V1V2 绕V1(V2)按逆时针方向旋转后遇到的第一条边。 图0-4双重连接边表的说明 从双重连接边表可以得到关联于给定顶点的边或者围绕一个给定面的边。假设G有n个顶点和 f个面，另外，数组HV［1..n］和HF［1..f］分别是顶点和面表的首标，用O(n)时间扫 描数组V1和F1能填满这些数组。下述过程产生关联于vj的边序列。 procedure VERTEX(j) begin a←HV［j］； a0←a； A［1］←a； i←2； ifV1［a］=jthena←P1［a］e lsea←P2［a］； whilea≠a0do A［i］←a； ifV1［a］=jthena←P1［a］els ea←P2［a］； i←i+1 end VERTEX(j)的执行时间和关联于vj的边数成比例。把上述过程中的HV和V1分别换成HF 和F1，即可得到围绕fj的边序列。 边表是描述平面图G的另一种形式，对于每个顶点Vj∈V，边表包含与Vj关联的边，且这 些边按逆时针方向排列。显然耗费O(V)时间可以把G的边表转换成双重连接边表。 0.2相关的几何知识 0.2.1基本定义 本书考虑的对象是欧几里得空间的点集，包含通过两个给定点的直线、直线上两定点确定的直线 段、3个给定点确定的平面及由有序点列确定的多边形，等等。另外，假设有一个坐标系， 使得每个点表示为相应维数的笛卡儿坐标的向量。我们还约定点集是有限可列举的。本节将 简要回顾相关的几何知识，其细节请参见有关资料。 用Ed(或Rd)表示d维欧几里得空间，即具有度量∑di=1x 2i1/2的实数xi(i=1,d)的d元组(x1，x2,…，xd)的空间。 下面给出本书所涉及的基本对象的定义。 (1) 点用p表示一个点，Ed中的点p定义为一个d元组(x1，x2,…，xd) 。点p也可解释为有d个分量的向量，此向量的起点为坐标原点，终点为点p。 (2) 线，线性簇在Ed中给定两个不同的点p1和p2，线性组合 αp1+(1-α)p2(α是实数，即α∈R)(0-1) 是Ed中的一条线。如果给定Ed中k个线性独立的点p1，p2,…，pk(k≤d)，则线性组合 α1p1+α2p2+…+αk-1pk-1+(1-α1-…-αk-1)pk( αi∈R) 是Ed中的(k-1)维的线性簇。 (3) 线段在Ed中给定两个不同的点p1和p2，若在式(0-1)中加入 条件0≤α≤1，则得到p1和p2的凸组合，它描述了连接两点p1和p2的直线段，并记 为p1p2(无序对)。 (4) 凸集设D是Ed中的域，且p1和p2是D中的任意两点，如果线段 p1 p2完全包含在D中，则域D是凸的。 可以证明，两个凸域的交是一个凸域。 (5) 凸壳Ed中点的集合S的凸壳是Ed中包含S的最小凸域的边界。 (6) 多边形多边形定义为线段的有限集合，该集合中每条线段的端点恰 好为两条边所共有，而且没有边的子集具有这个性质。线段为多边形的边，其端点是多边形 的顶点，而且顶点数和边数相等。 若多边形的不相邻边对不相交，则称该多边形为简单多边形。简单多边形把平面划分为两个 不相交的区域： 内部区域(有界的)和外部区域(无界的)。一般情况下，多边形理解为边界和 内部区域的并。 若简单多边形P的内部区域是凸集，则称P是凸的。如果P内存在点q，使得对于P的所有点p， 线段qp完全位于P内，则此简单多边形是星形多边形。具有上述性质的q的轨迹 称为P的核。 (7) 平面图若图G=(V,E)能不交叉地嵌入平面，则G是平面图。平面图的 直线平面嵌入确定平面的一个划分，称为平面剖分。设平面图的顶点数、边数和区域数分别 为v，e和f，则由欧拉公式有 v-e+f=2(0-2) 如果每个顶点的度数≥3，则v,e和f是两两成比例的。 (8) 三角剖分若平面剖分的所有有界区域是三角形，则此平面剖分称为 三角剖分。有限点集S的三角剖分是S上具有最大边数的平面图。或者说，由不相交的直线段 来连接S的点得到S的三角剖分，以至于每个三角形区域都在点集S凸壳的内部。 (9) 多面体E3中，多面体定义为平面多边形的一个有限集，并且多边 形的每条边和相邻的另一个多边形共有，而且没有多边形子集具有相同的性质。多边形的顶 点和边是多面体的顶点和边； 多边形是多面体的小面。 多面体中，如果没有不相邻的小面对共点，则此多面体称为简单多面体。简单多面体将空间 划分为不相交的两部分(有界的内部域和无界的外部域)。一般说来，多面体是指边界和内部 域的并。