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 in Canada + 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.