Real Geometry and Connectedness via Triangular Description

连通性，就像“我们能从这里到达那里”一样，是一个基本的概念，无论是在实际空间还是在各种抽象空间中。想想直角走廊里的一架长梯子：它能绕过拐角吗？称它为走廊意味着它是在实际的三维空间中连接起来的。但是，如果我们考虑梯子外形的空间，这是由梯子的位置和方向决定的，而“走廊”现在是要求梯子的任何部分都不能撞到墙上--梯子的两端没有墙壁是不够的。如果梯子太长，它可能有两个可行的位置，在走廊的每一臂上一个，但可能没有可能的方法从一个到另一个。在这种情况下，我们说梯子的配置空间没有连接：我们不能从这里到那里到达梯子，即使我们可以从这里到那里(分开取，这在物理上是不可能的)。因此，构形空间的连通性是运动规划的关键。这些都是人类(尤其是搬家具的人，或者试图把车停在狭小空间里的人)凭直觉解决的问题，但却很难解释。请注意，阶梯是刚性的和三维的，因此它的位置由上面三个点的坐标确定，所以配置空间是九维的。数学空间的连通性也很重要。4的平方根可以是2也可以是-2：我们必须决定哪一个。同样，9的平方根可以是3或-3。但是，在我们的问题空间中，如果4与9相连(不管是什么)，我们不能独立地做出这些选择：我们的选择必须在从4到9的道路上保持一致。当不可能完全一致地做出这样的决定时，我们就有了数学家所说的“分支切割”--国际日期变更线就是典型的例子，因为不可能在全球范围内一致地分配“日”。在以前的工作中，我们已经证明了几个数学悖论归结为适当空间中的连通性问题，该问题被相关的分支切割所划分。这是一个出了名的难以手工掌握的数学领域，数学家和软件包在涉及到分支切割时往往存在内部不一致。自20世纪80年代初以来在运动规划中提出的连通性的标准计算方法是通过一种称为柱面代数分解的技术。这在历史上是通过“自下而上”的方法计算的：我们首先分析一个方向，比如x轴，将其分解成所有必要的临界点和中间区域，然后将每个(x，y)圆柱体置于每个临界点或区域之上，并将其分解，然后将每个(x，y，z)圆柱体置于每个这些区域之上，依此类推。这不仅听起来单调乏味，而且不可避免地乏味--调查人员和其他人已经证明，这个问题极其困难(维度数量呈双指数增长)。很多时候，特别是在运动规划中，我们实际上对低维组件并不感兴趣，因为它们对应的是没有自由度的运动，而不是走钢丝。加拿大最近的发展显示了一种通过所谓的三角分解来计算这种分解的替代方法，2010年的一篇论文(加拿大的Moreno Maza+Davenport)表明，三角分解的最高维分量可以在单指数时间内计算出来。因此，这开启了我们打算研究的在单指数时间内计算圆柱分解的最高维分量的前景，这将是计算几何学的重大突破。

Connectedness, as in "can we get there from here", is a fundamental concept, both in actual space and in various abstract spaces. Consider a long ladder in a right-angled corridor: can it get round the corner? Calling it a corridor implies that it is connected in actual three-dimensional space. But if we consider the space of configurations of the ladder, this is determined by the position and orientation of the ladder, and the `corridor' is now the requirement that no part of the ladder run into the walls - it is not sufficient that the ends of the ladder be clear of the walls. If the ladder is too long, it may have two feasible positions, one in each arm of the corridor, but there may be no possible way to get from one to the other. In this case we say that the configuration space of the ladder is not connected: we can't get the ladder there from here, even though we can get each end (taken separately, which is physically impossible) from here to there. Connectedness in configuration space is therefore the key to motion planning. These are problems human beings (especially furniture movers, or people trying to park cars in confined spaces) solve intuitively, but find very hard to explain. Note that the ladder is rigid and three-dimensional, hence its position is determined by the coordinates of three points on it, so configuration space is nine-dimensional.Connectedness in mathematical spaces is also important. The square root of 4 can be either 2 or -2: we have to decide which. Similarly, the square root of 9 can be 3 or -3. But, if 4 is connected to 9 in our problem space (whatever that is), we can't make these choices independently: our choice has to be consistent along the path from 4 to 9. When it is impossible to make such decisions totally consistently, we have what mathematicians call a `branch cut' - the classic example being the International Date Line, because it is impossible to assign `day' consistently round a globe. In previous work, we have shown that several mathematical paradoxes reduce to connectedness questions in an appropriate space divided by the relevant branch cuts. This is an area of mathematics which is notoriously difficult to get right by hand, and mathematicians, and software packages, often have internal inconsistencies when it comes to branch cuts. The standard computational approach to connectedness, which has been suggested in motion planning since the early 1980s, is via a technique called cylindrical algebraic decomposition. This has historically been computed via a "bottom-up" approach: we first analyse one direction, say the x-axis, decomposing it into all the critical points and intermediate regions necessary, then we take each (x,y)-cylinder above each critical point or region, and decompose it, then each (x,y,z) above each of these regions, and so on. Not only does this sound tedious, but it is inevitably tedious - the investigators and others have shown that the problem is extremely difficult (doubly exponential in the number of dimensions).Much of the time, notably in motion planning, we are not actually interested in the lower-dimensional components, since they would correspond to a motion with no degrees of freedom, rather like tightrope-walking. Recent Canadian developments have shown an alternative way of computing such decompositions via so-called triangular decompositions, and a 2010 paper (Moreno Maza in Canada + Davenport) has shown that the highest-dimensional components of a triangular decomposition can be computed in singly-exponential time. This therefore opens up the prospect, which we propose to investigate, of computing the highest-dimensional components of a cylindrical decomposition in singly-exponential time, which would be a major breakthrough in computational geometry.