论文标题
圆柱形代数分解与边界状态
Cylindrical Algebraic Decomposition With Frontier Condition
论文作者
论文摘要
圆柱代数分解（CAD）是R^n分解为有限的半ge骨细胞集合。如果对于每个细胞C，则有一个分解的单元集合，其结合的结合是C的闭合。该特性在其他文献中称为“封闭有限的”或“边界连贯性”，则CAD满足“边界条件”。本文证明了并提出了一种构建算法，它可以满足边境条件，而没有坐标的初步变化，例如在潜在的爆破存在下。该算法具有基本的（在Kalmar的意义上）。这也为带有此特性的CAD中的单元格数提供了上限。边界条件可用于计算由一阶公式定义的半格式集合的拓扑特性，在解决运动计划问题和可定义的单调家族的三角剖分方面。提出的算法采用了一种新颖的方法，因为它在初始分解中使用了细胞指数词典的递归。
A Cylindrical Algebraic Decomposition (CAD) is a decomposition of R^n into a finite collection of semialgebraic cells. A CAD satisfies the "frontier condition" if, for every cell C, there is a collection of cells of the decomposition whose union is the closure of C. This property is referred to in other literature as "closure finiteness" or "boundary coherence". This paper proves the existence of, and presents an algorithm to construct, a CAD satisfying the frontier condition without a preliminary change of coordinates, e.g., in the potential presence of blow-ups. The algorithm has elementary (in the sense of L. Kalmar) complexity. This also provides an upper bound on the number of cells in a CAD with this property. The frontier condition can be useful in computing topological properties of semialgebraic sets defined by first-order formulas, in solving motion planning problems and in triangulations of definable monotone families. The algorithm presented takes a novel approach in that it uses a recursion on the lexicographical order of cell indices in the initial decomposition.
