Certain plane/space partitions defined by the arrangement of a set of objects or by distance/ Voronoi diagrams, are important in collision detection and robot navigation. One innovative aspect is to combine rigorous algebraic tools, such as resultant theory and methods from Real Algebraic Geometry, with fast approximate numerical computation, including iterative methods and approximation techniques. We expect that original research can be conducted in both directions, yielding tools that exploit the geometric structure of the problem at hand. A relevant question is the trade-off between performance enhancement and limited precision or approximate output.

In particular, our algebraic tools include resultants and subdivision solvers. Resultants provide a compact way for characterizing the solvability of a polynomial system and lead to efficient ways for describing the common roots. Polynomial systems that are relevant to CAD applications will be studied, such as multi-homogeneous systems, so as to exploit their structure and obtain compact matrices. Subdivision solvers are very relevant for geometric computing, since they provide methods to localize roots in a bounded real domain, and have seen important progress lately. They can be used as filters in many geometric operations, such as detecting characteristic points on a shape, as well as for providing certified approximations of the solutions of polynomial systems.

Another innovative aspect is the end-to-end process, starting with the design of efficient algorithms and leading to robust and general implementations. Here, different software packages must collaborate. On the one hand we will use the INRIA software SYNAPS for supporting the algebraic operations, with which we have long experience. On the other hand, we would need some geometric software, which might be one of the platforms developed by other (industrial) SAGA partners, chosen depending on the specific application.

For more details contact: