Cylindrical Algebraic Decomposition

圆柱代数分解是一种通用的计算技术，它支撑着实代数几何中的许多问题及其应用，例如：机器人运动规划。产生这种分解有各种各样的算法。然而，所有已知的算法产生的对象，当柱面代数分解时，也满足某些其他性质。这些通常没有很好地表达出来，我们希望做到这一点。由于柱面代数分解定义的通用性，许多问题，如邻接性，目前还没有解决。我们认为，对实践中产生的分解类型进行更精确的描述，将使生成在应用中非常有用的算法变得更容易。巴斯团队基于McCallum的投影作为构建此类CAD的工具，在CAD方面取得了许多进展。但麦卡勒姆的预测可能会失败。最近，麦卡勒姆和他的同事已经证明，不同的投影（拉扎德的投影），以及相关的不同提升算法，永远不会失败。项目的开始阶段围绕着收集有关CAD的背景信息，特别是围绕McCallum和Lazard的投影。在这个阶段，我将参加计算机科学系三年级的计算机代数课程，因为它涵盖了CAD的基础知识。除了CAD之外，我还将根据项目范围的需要扩大我在代数几何方面的知识，并将参加在巴斯大学举行的定期几何研讨会。作为一个起点，我将把我的注意力集中在理解钢琴移动器的问题上，这个问题问的是，给定一个物体和它的构型空间，是否有可能将物体从a点移动到b点。如果这是可能的，那么最有效的方法是什么？

Cylindrical Algebraic Decomposition is a general-purpose computation technique underpinning many questions inreal algebraic geometry and its applications,e.g. robot motion planning. There are various algorithms for producing such decompositions. However, all knownalgorithms produce objects which,while Cylindrical Algebraic Decompositions, also satisfy certain other properties. These are generally not wellarticulated,and we would like to makethis precise. Many issues, such as adjacency, are currently not solved for Cylindrical Algebraic Decompositions,because of the generality of the definition.We suspect that having a more precise description of the sort of decompositions produced in practice would make iteasier to produce algorithms that are veryuseful in applications. The Bath group have made many developments in CAD based on McCallum's projection as atool for constructing such CADs. But McCallum'sprojection can fail. Recently McCallum and colleagues have proved that a different projection (Lazard's), andassociated different lifting algorithms, never fails.The starting phase of the project revolves around gathering background information regarding CAD, specificallyaround McCallum's and Lazard's projection. During this phase I willbe attending the computer algebra course offered to third years in the computer science department as this coversthe basics of CAD. Apart from CAD I will be broadening myknowledge in Algebraic Geometry, as required by the scope of the project, and will be attending the regular geometryseminars that are held at the University of Bath.As a starting point I will be focussing my attention towards understanding the piano mover's problem, which askswhether, given an object and its configuration space,it is possible to move the object from point A to point B. If this is possible what is the most efficient way to do so?