通用数字拓扑结构的基本公理：离散模型和基本结果

73理论计算机科学电子笔记46（2001）网址：http://www.elsevier.nl/locate/entcs/volume46.html20页通用公理化数字表面结构S'ebastienFourey1，2，T. YungKong3，Ga b或T. Herman赫尔曼4，5天普大学计算机科学与应用数学中心，费城，PA 19122，美国。摘要在数字拓扑学中，欧氏n-空间Rn通常由离散网格的点集或由其并集为Rn的凸胞元复体中的n-胞元集来建模。对于n=2和3的常用网格和复形，已知网格点或n-胞元上的某些邻接关系对（κ，λ）（如Z2上的（4，8）和（8，4））是“好对”.对于这些关系对（κ，λ），许多关于一组格点或n-胞元及其补集的数字拓扑结果（如罗森菲尔德目前，二维和三维数字拓扑的结果通常是针对一对好的邻接关系一次- 因此，对于每个结果，对于不同的好的邻接关系对，都有不同的（但类似的）定理。在本文中，我们采取的第一步，在发展一种替代方法的数字拓扑结构的基础上非常普遍的公理定义的“良好的数字空间”。这种方法给出了陈述和证明结果的数字拓扑作为单一的定理，适用于所有空间的适当维数，满足我们的公理的可能性。具体来说，本文介绍了一个通用的公理化数字表面结构（GADS）的概念-一个一般的，公理化定义的，类型的离散结构，模型的子集的欧几里得平面和其他表面。这一概念的扩展包括对应于所有良好的相邻关系对的GADS，这些相邻关系对以前在平面网格和边界表面上的数字拓扑中使用过（由我们自己或他人使用）。我们定义了GADS的基本概念（如同伦的路径和交叉数的两个路径），给出了一个离散的定义的平面GADS（这是GADS模型的子集的欧几里德平面），并提出了一些基本结果，包括约旦曲线定理的平面GADS。1电邮地址：邮箱：llaic.u-clermont1.fr或fourey@greyc.ismra.fr2SupportedbyaLavoisiergranntfromtheMinist'eredes A souvenairesE'transg'eres，France.3永久地址：纽约市立大学皇后学院计算机科学系，Flushing，NY 11367，U.S.A.电子邮件地址：ykong@cs.qc.edu4电子邮件地址：gaborherman@netscape.net5美国支持NIH资助HL-28438和美国NSF授予DMS-9612077。2001年由ElsevierScienceB出版。 诉 在CCBY-NC-ND许可下开放访问。福雷、孔和赫尔曼74{∈|}1介绍在数字拓扑学中，欧氏n-空间Rn通常由离散网格的点集或由其并集为Rn的凸胞元复体中的n-胞元集来建模。欧几里德n-空间中的连通性通常由图论中的连通性概念来建模，这些连通性概念来自于在网格点或n-单元上定义的邻接关系。对于n= 2和3的情况下的常用网格和复形，已知网格点或n-单元上的某些邻接关系对（κ，λ）是“好对”。对于这些关系对（κ，λ），许多关于一组格点或n-胞元及其补集的数字拓扑的结果都有这样的版本，其中κ-邻接被用来定义集合上的连通性，λ-邻接被用来定义补集上的连通性例如，（4，8）和（8，4）是Z2上的好的邻接关系对.因此，罗森菲尔德如果4-或8-邻接中的同一个用于两个目的，则该定理无效：（4，4）和（8，8）不是Z2上的好对.一些邻接关系与自身形成良好的配对。这种良好对的示例是2D六边形网格的网格点上的对（6，6）。(The网格点是由正六边形平铺的欧几里得平面中的六边形的中心，并且如果两个点是共享边的六边形的中心，则它们是6-相邻的。）另一个例子是Z2上的好对（κ2，κ2），其中κ2是Z 2上的Khalimsky如下：假设Z2的一个点是纯的，如果它的坐标都是偶数，或者既奇怪又混杂则Z2的两个点是κ2-相邻的，如果它们是4-相邻的，或者如果它们是纯点并且是8-相邻的。在三维空间中，（6，26），（26，6），（6，18），（18，6）是Z3上的好邻接关系对.Z3上的一个好对的不同例子是（κ3，κ3），其中κ3是κ2的三维类似物：Z3上的两个点是κ3-相邻的，如果它们是6-相邻的，或者如果它们是26-相邻的，并且两个点中至少有一个是纯点，其中纯点是坐标全奇数或全偶数的点（12， 12），（12， 18）和（18， 12）是3D面心立方网格（例如，对（x，y，z）Z3x + y + z0（mod 2））和（14，14）是3D体心立方网格的点上的良好对(e.g.、on {（x，y，z）∈Z3|xyz（mod 2）}）。目前，二维和三维数字拓扑学的结果通常是针对一对好的邻接关系一次证明的，6如果α是一个在集合G上的非自洽对称二元关系，G是一个笛卡尔或非笛卡尔格网，则α称为G上的k-邻接关系，用整数k中的p表示，如果对所有p∈G，|pαq}n只包含k个点，并且它们都严格地比G p中的任何其它点更接近p（在欧氏距离中）.福雷、孔和赫尔曼75对于不同的好对，可能是显著不同的。在3D网格的情况下，即使我们只考虑上面提到的九对好的邻接关系，一个结果，如数字约旦曲面定理，将被期望有九个不同的版本，九个单独的证明！我们认为，这种情况是不能令人满意的。我们已经开始考虑数字拓扑学的另一种方法，在这种方法中，“行为良好”的数字空间被公理化地定义，使用的公理足够普遍，可以接纳与上述良好邻接关系对相对应的数字空间。这种方法允许2D或3D数字拓扑的结果被证明为满足适当假设的所有行为良好的空间的单个定理(Our乔丹曲线定理（下面的定理4.7）说明了这一点。）在本文中，我们将注意力集中在模拟欧几里得平面和其他曲面子集的数字空间上，并给出了这类空间的一个非常一般的公理化定义，它包括与二维数字拓扑文献中使用的所有好的邻接关系对相对应的空间（包括平面和边界曲面）。满足我们公理定义的空间称为GADS。正如我们在2.5节中所看到的，我们在定义GADS时所使用的数学框架的很大一部分已经被第三作者[4，5]使用过作为发展这些空间的数字拓扑的第一步，我们定义了GADS上两条路径的交集数，并概述了证明该数在两条路径的同伦变形下不变的证明。这主要是对第一作者和Malgouyres在[1，2，3]中给出的定义和定理的任意推广。我们还给出了一个（离散）的平面GADS，模型的子集的欧几里德平面的定义，并提出了一个约旦曲线定理，这样的GADS。与第二作者的一些早期工作相比（例如，[7，8，9]），本文不使用任何基于数字空间的多面体连续类似物的论证，而只使用离散论证。2GADS和pGADS2.1基本概念和符号对于任何集合P，我们用P{2}表示P的所有不同元素的无序对的集合（等价地，P的所有子集正好有两个元素的集合）。 设P为任意集合，且ρ∈P{2}。图7P的两个元素a和b[分别，P的两个子集A和B]被称为ρ-相邻，如果{a，b} ∈ρ[分别地，如果存在a∈A和b∈B，且{a，b} ∈ρ]。如果x∈P，我们用Nρ（x）表示P中与x相邻的元素的集合;这些元素也被称为x的ρ-邻居。我们称Nρ（x）为穿孔的7ρ可以看作是P上的一个二元的、对称的、不相关的关系，（P，ρ）可以看作是一个无向简单图.福雷、孔和赫尔曼76⊆| |联系我们联系我们x的p-邻域从a∈P到b∈P的ρ-路是一个有限序列（x0，.，xl），使得x0=a，xl=b，并且对于所有i∈ {0，.，l− 1}，{xi，xi+1} ∈ρ. 非负整数l是路径的长度长度为0的路径称为单点路径。对于所有的整数m，n，0 ≤m≤n≤l，子序列（x m，.，xn）的（x0，...，x l）称为区间或段对于所有i∈ {1，.，l}我们说元素x i−1和x i在路径上是连续的，并且在路径上x i−1在x i之前，x i在x i−1之 后 。注意，ρ-路的连续元素永远不可能相等。ρ-路（x0，.，xl）被称为是简单的，如果对于{0，.，l}。如果x0=xl，则称它是闭的，因此x0跟随x l−1。它被称为ρ-圈，如果它是闭的，并且对于{1，...，l}。单点路是最简单的ρ-圈。 两个ρ-圈c1=（x0，...，xl）并且c2=（y0，...，y1）被称为是等价的，如果存在整数k，0 ≤k≤l−1，使得x i=y（i+k）modl，对于所有i∈ {0，.，l}。如果S P，则称S的两个元素a和b在S中是ρ-连通的，如果存在从a到b的仅由S中的点组成的ρ-路。 ρ-连通性是S上的一个等价关系;它的等价类称为S的ρ-分支。称集合S是ρ-连通的，如果S只有一个ρ-分支。给定两个序列c1=（x0，.，xm）和c2=（y0，...，yn）使得xm=y0，我们用c1.c2表示序列（x0，...，x m，y1，.，y n），我们称之为C1和C2的连锁。当我们使用符号c1.c2时，我们也隐含地说c1的最后一个元素与c2的第一个元素相同。显然，如果c1和c2是长度为l1和l2的ρ-路，则c1.c2是一条长度为l1+l2的ρ路。对于任意序 列c= （ x0，.，x m），c的倒数，用c−1表示，是序列（y0，...，y m）使得y k=xm-k对于所有k 0，...，M. 显然，如果c是长度为l的ρ-路，那么c−1也是。简单闭ρ-曲线是一个非空的有限ρ-连通集C，使得C的每个元素在C中恰好有两个ρ-近邻。(Note一条简单的闭ρ曲线必须至少有三个元素。一个长度为C的ρ-圈c包含一条简单闭ρ-曲线C的所有元素，称为ρ-参数化梭注意，如果c和cJ是简单闭ρ曲线C的ρ参数化，则cJ等价于c或c−1。如果x和y是简单闭ρ-曲线C上的ρ-相邻元素，则我们可以说x和y在C上是ρ-连续的。如果x和y是简单闭ρ-曲线C上不ρ-连续的不同元素，则Cx，y的两个ρ-分量中的每一个都称为与x和y相关联的（C的）ρ-截区间。福雷、孔和赫尔曼77∩LLLL∈\2.2GADS的定义定义2.1（2D数字复数）2D数字复数是一个有序三元组（V，π，L），其中• V是一个集合，其元素称为顶点或拼块，• π<$ V{2}，π中的顶点对称为原边，• L是一组简单的闭π-曲线，其成员称为回路，以下四个条件成立：(i) V是π连通的，并且包含多个顶点。(ii) 对于任意两个不同的环L1和L2，L1L2要么是空的，要么是由一个顶点组成的，要么是一条原边。(iii) 在两个以上的循环中不包含原边(iv) 每个顶点只属于有限数量的原边。指定顶点集为点集的2D数字复合体时对于Rn中的网格，可以使用正整数k（例如4、8或6）来表示所有k个相邻顶点的无序对的集合我们写L2×2来表示Z2中所有单位格的集合。三元组（Z2，4，2×2）是一个简单的2D数字复合体的例子。定义2.2（GADS）通用公理化数字表面结构或GADS是对G =（（V，π，），（κ，λ）），其中（V，π，）是2D数字复合体（其顶点、原边和环也被称为G的顶点、原边和环），并且其中κ和λ是满足下面的公理1、2和3的V { 2 }的子集。 κ和λ中的顶点对称为κ-边和λ-边缘。 （V，π，L）称为G的基础复形。公理1每个原边都是κ-边和λ-边：π <$κ<$λ。公理2对于所有e ∈（κ<$λ）\π，某个环包含e的两个顶点。公理3如果x，y∈L∈ L，但x，y在L上不是π-连续的，则(a) {x，y}是λ-边当且仅当L\{x，y}不是κ-连通的。(b) {x，y}是κ边当且仅当L\{x，y}不是λ-连通边。关于公理2，请注意，如果e（κ λ）π（即， e是κ-或λ-边，但不是原边），则根据2D数字复形定义中的条件（ii），只能有一个包含e的两个作为公理3的例证，观察到（（Z2，4，L2×2），（4， 8））和（（Z2，4，L2×2），（8， 4））都满足公理3，但是（（Z2，4，L2×2），（4， 4））违反公理3的“如果”部分，而（（Z 2，4，2×2），（8，8））违反公理3的公理一个GADS被称为有限的，如果它有无限多的顶点;否则，它是据说是无限的。所有GAD的集合可以如下排序：定义2.3（n阶，subGADS）设G=（（V，π，L），（κ，λ））并且GJ=福雷、孔和赫尔曼78LLLLLL{{}|}22（（VJ，πJ，LJ），（κJ，λJ））是GADS，使得• V<$ VJ，π<$ πJ和L <$LJ。• 对于所有L ∈ L，κ <$L{2}= κ J<$L{2}且λ <$L{2}= λJ<$L{2}。然后我们写G <$G J，说G是Gj的子GADS。 我们也称G为由（V，π，L）诱导的Gj的子GADS。 我们写G <$G j表示G <$G J，G=/GJ。 我们写G3，则根据引理6.3，C是一条简单的闭（κ λ）曲线，因此x，y κ λ，所以结果由公理3得出。✷7交叉点编号设G=（（V，π，λ），（κ，λ））是一个可定向GADS，λ是G的一个凝聚定向.在这一节中，我们定义一条（κ λ）-路p与一条闭（κ λ）-路c的交集数，我们用I表示。路口若两条路的每一公共点是G的非奇异内点，则定义数。不严格地说，它是路径p从封闭路径c的右边到它的左边穿过的次数，减去p从左到右穿过c我们的交集数是数字边界中曲面路径之间交集数的推广，在[1，2]中定义和使用，除了我们只定义两条路径之一闭合时的交集数。8我们关于交数的主要结果（定理7.7）是：在可定向GADS中，λ-路与闭κ-路的交数在λ-路的λ-同伦变形下不变，假设闭κ-路的所有顶点都是非奇异内部G的顶点正如我们将在下一节中看到的，这个事实可以用来证明我们关于平面GADS的Jordan曲线定理（定理4.7）。交数的定义是基于这样的思想：对于（κ∈λ）-路的每个三顶点段（x0，x1，x2），其中x1是G的非奇异内顶点，我们可以将集合NL（x1）\{x0，x2}划分为和相对于线段（x 0，x 1，x 2）的[8]很容易将我们的定义扩展到两条不封闭的路径福雷、孔和赫尔曼88{}（y，z）（y，z）∪∪∪∪c1，c2=−IΩΩΩΩΩ（y，z）ΩΩc，pc，p2c，p1ΩN，x0（x1），定义见5.2节。这方面的细节将在下一个定义中给出。注意，由于{x0，x1}，{x1，x2} ∈κ∈λ，公理2意味着x0，x2∈NL（x1），使得x2位于π-圈NL，x0（x1）上。定义7.1设（x0，x1，x2）是（κ <$λ）-路的一段，其中x1是G的一个非奇异内点，设N<$，x0（x1）=（v0，.，v n），所以v0=v n=x0。设h∈ {0，.，n}是使得v h=x2的整数。然后