Cylindrical Algebraic Decomposition

点击翻译按钮获取中文摘要

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?