Algorithmic Triangulation of Monotone families

拟议的研究是在计算机代数领域，这是计算机科学系数学基础小组的主要研究领域之一。它的核心思想是，一旦半代数集被分解成足够简单的片段，它们就会变得更容易处理。柱面代数分解(CAD)就是这样的方法之一，它将半代数集分解成柱面单元。这种方法得到了很好的研究，可以构造任意半代数集的计算机辅助设计。然而，有时会出现具有不良特性的CAD。例如，并非CAD中的所有单元格都具有拓扑规则单元格的属性。Basu，Gabrielov和Vorobjov证明了对于一个具有$-dim(K)-2$的半代数集$K-子集R^n-$，总是可以构造出一个具有所有拓扑正则胞元的CAD。这个项目的第一个目标是设计和实现一个有效的算法来构造这些规则的CAD。高效地构造规则CAD的能力本身就是一个重要的问题，但它也是我研究的第二个目标的依赖。巴斯大学还参与了EPSRC的一个项目，名为《推回柱面代数分解的双指数墙》。研究的第一部分，设计了一种高效的生成规则CAD的算法，很好地符合这个项目。另一种分解半代数集的方法是三角剖分。与CAD一样，有一些经典的结果表明，任何半代数集都可以三角剖分。然而，在许多拓扑问题中，单调族对集合的逼近是有用的。当崩盘发生时，这些家庭的行为可能会很复杂，尝试将它们归类为有限数量的标准类型可能会有所帮助。Basu，Gabrielov和Vorobjov还证明了可以构造一个从二维单调族到单纯复形的三角剖分，使得每个2-单调复形都有五种类型之一。我的下一个研究目标是利用这一结果并利用它来设计一个构造满足上述条件的三角剖分的算法。规则CAD的构建将是这一过程的中间步骤。如果时间允许，也有可能将上述算法扩展到维度为3的集合，甚至可能推广到n维集合。这项研究的一个具体目标是考虑将这些新算法包括在计算机代数系统中的可能性，如Maple。这将使它们能够被其他研究人员在更广泛的应用中使用。例如，可以使用CAD算法来执行量词消除。这具有广泛的应用范围，从安全关键软件系统的验证到生物学和经济学中的新兴应用。

The proposed research is in the field of computer algebra, one of the main areas of research within the Mathematical foundations group in the Department of Computer Science.It is centred around the idea that semi algebraic sets become easier to work with once they have been broken down into sufficiently simple pieces.One such method is Cylindrical Algebraic Decomposition (CAD), which breaks a semi algebraic set into cylindrical cells. This method is well studied, and it is possible to construct a CAD of any semi algebraic set. However sometimes CADs can arise which have undesirable properties. For example, not all cells in the CAD have the property of being topologically regular cells. Basu, Gabrielov and Vorobjov proved that for a semi algebraic set $K \subset R^n$ with $\dim(K) \le 2$ it is always possible to construct a CAD with all topologically regular cells. The first objective of this project is to design and implement an efficient algorithm to construct these regular CADs. The ability to efficiently construct regular CADs is an important problem in it's own right, but it is also a dependency for the second aim of my research.The University of Bath is also involved in an EPSRC project entitled "Pushing Back the Doubly-Exponential Wall of Cylindrical Algebraic Decomposition". The first part of my research, designing an efficient algorithm for creating regular CADs fits in nicely with this project.Another method of breaking up semi algebraic sets is triangulation. As with CAD, there are classical results that state that any semi algebraic set can be triangulated. However, in a number of topological problems, approximations of sets by monotone families are useful. When blow-ups occur, the behaviour of these families can be complex, and it can help to try to classify them into a finite number of standard types. Basu, Gabrielov and Vorobjov also proved that a triangulation of a 2-dimensional monotone family into a simplicial complex can be constructed such that each of the 2-simplices will have one of five types. The next objective of my research is to take this result and use it to design an algorithm for constructing triangulations which satisfy the above condition. The construction of a regular CAD will be an intermediate step in this process.If time allows, there is also a possibility of extending the above algorithms to sets with dimension <= 3, and possibly even generalising to n-dimensional sets.A tangible objective of this research is to consider the possibility of including these new algorithms in computer algebra systems, such as Maple. This will enable them to be used by other researchers in wider applications. For example, the CAD algorithm can be used to perform quantifier elimination. This has a broad array of applications, ranging from verification of safety-critical software systems to emerging applications in biology and economics.