Real Geometry and Connectedness via Triangular Description

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.

Real geometry, i.e. the geometry of space as we perceive it without complex numbers, is vital to much of mathematics and many applications despite being less studied/taught (because it is harder?) than complex geometry. Solving problems in real geometry tends to lead to a lot of special cases (see (2) in the case for support), and is tricky to do by hand. Hence there are potentially many application areas for better algorithmic methods for real geometry and connectedness. In particular the question of interest is "connectedness within the reals": it is no good telling a robot to turn through an imaginary angle.

A) The theory of cylindrical algebraic decomposition was originally invented to solve the quantifier elimination problem: given a sentence containing "for all " or "there exists" clauses, produce an equivalent sentence without such clauses. Note that many sentences which appear not to contain such clauses in fact do: the [false over the reals] statement "sin is an invertible function" is really "for all y there exists an x such that y = sin(x)". Hence there are numerous applications in logic and computational mathematics which can benefit from better cylindrical algebraic decomposition: both in the U.K. and world-wide.

B) Motion planning for robots and similar devices such as automatically-steered cars, can be seen, as in [32], as "connectedness in configuration space", i.e. "can we get there from here", where "here" and "there" are configurations of the robot, rather than simply spatial points. This "configuration space" is typically of much higher dimension than one might expect: a rigid body in three-dimensional space is defined by three points, i.e. nine dimensions in all. Hence it is very important to have algorithms which behave efficiently as the number of dimensions grows, and this project should produce such algorithms. Motion planning is one of the areas we have worked on in the past [17], and we intend to pursue exemplar case studies ourselves, as well as disseminating our work via the IMRCs and appropriate conferences.The benefits of better motion planning are incalculable, ranging from better housework robots to the "Factory of the Future". Reconfiguring a "Factory of the Future" requires off-line motion planning, a "motion compiler", which would be a major gain: achievable via the use of the Maple software we will deliver. Further down the line one might envisage on-line motion planning, where our improvements in algorithmic performance would be even more significant.

C) Many mathematicians, and users of mathematics, have problems with apparently-simple function definitions. It is impossible to define 'square root' as a continuous function on the whole complex plane, since the argument of the square root of x is half the argument of x, and therefore the square root of 1 could be either 1 or -1, and neither choice is consistent with continuity. Hence one has to introduce 'branch cuts', and say that the definition is discontinuous as one crosses this cut. These cuts mean that many formulae are not in fact correct, either for special values ("log(1/x)=-log(x)" is not true when x=-1), or in much of the complex plane ("sqrt(x**2-1)=sqrt(x-1)sqrt(x+1)" is only 50% true). The Bath team [1-8] have realised that this is a question of connectivity of the complement of the branch cuts. This has been implemented, and provides a much better (guaranteed never to state that an incorrect identity is true) simplification algorithm than previous ones. However, it is limited by the connectivity question, and the breakthrough envisaged in this project will make the connectivity approach to simplification much more feasible. Maplesoft (see letter of support) would be very interested in this, and where one leading vendor goes, others will follow.

All categories of users will benefit from our twin-track approach of scientific publication and software dissemination via the world-wide Maple computer algebra system.