Algorithmic Triangulation of Monotone families

计算机代数是计算机科学系数学基础小组的主要研究领域之一，其研究重点是将半代数集合分解为足够简单的部分，使其更容易处理。其中一种方法是圆柱形代数分解（CAD），它将半代数集合分解为圆柱形单元。这种方法是很好的研究，它是可能的，以建立一个CAD的任何半代数集。然而，有时CAD可能会出现具有不期望的属性。例如，并非CAD中的所有单元都具有拓扑规则单元的特性。Basu，Gabrielov和Vorobjov证明了对于一个半代数集$K \subset R^n$，$\dim（K）\le 2$，总是可以用所有拓扑正则的单元来构造CAD。这个项目的第一个目标是设计和实现一个有效的算法来构造这些规则的CAD。有效地构造规则CAD的能力本身就是一个重要的问题，但它也是我研究的第二个目标的依赖。巴斯大学也参与了EPSRC的一个名为“推回圆柱代数分解的双指数墙”的项目。我的研究的第一部分，设计一个有效的算法来创建规则的CAD很好地适合这个项目。与CAD一样，有经典的结果表明任何半代数集都可以三角化。然而，在一些拓扑问题中，单调族的集合近似是有用的。当爆炸发生时，这些家庭的行为可能是复杂的，它可以帮助尝试将它们归类为有限数量的标准类型。巴苏、加布里洛夫和沃罗布约夫还证明了一个二维单调族到一个单纯复形的三角剖分可以被构造，使得每个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.