JCJC SIMI 2 - JCJC - SIMI 2 - Science informatique et applications

Singular Curves And Surfaces Topology – SingCAST

SingCAST

Singular Curves And Surfaces Topology

Efficient triangulation of singular curves and surfaces with topological guarantees.

The problem investigated in this project is the efficient triangulation of singular curves and surfaces with topological guarantees. In particular, all the components and all the singularities (self-intersection or cusp points) must be reported. In the general case, this problem has been intensively investigated with symbolic methods, but the high complexity of those approaches makes them impracticable on difficult instances. On the other hand, in many applications such as in mechanical design of robots, the singular curves and surfaces are not completely general, and are often the projection of smooth curves and surfaces from higher dimensions. <br /> <br />In this restricted framework, we speculated that numerical methods such as interval arithmetic or subdivision could be used to improve significantly the triangulation of singular curves and surfaces with topological guarantees. The goal of this project is (1) to intertwine numerical and symbolic approaches to design new efficient algorithms, (2) to apply these methods on mechanical design problems, and (3) to make these methods accessible in computer algebra systems and improve the state-of-the-art certified visualization libraries of singular curves and surfaces.

During the first 18 months of the project, we worked mainly on the problem of approximating a singular curve by a piecewise-linear curve with the same topology. Our work specifically addressed the case of a singular 2D curve that is the projection of a smooth 3D algebraic curve. In this case, we designed a new theoretical algorithm to isolate the singular points of the 2D curve, we implemented it and we demonstrated its efficiency with respect to the state-of-the-art implementations.

In particular, given P(x,y,z) and Q(x,y,z) two polynomials of degree d, we focused on the curve C defined by the set of real points (x,y) such that there exists z satisfying P(x,y,z) = Q(x,y,z) = 0. In practice, state-of-the-art approaches can only compute the singular points for d lower than 10. Our new method allowed us to compute the singular points for d = 12. Moreover, we extended our work to analytic functions and we developed a new method to compute the singularities of C in the case where P and Q are analytic functions, i.e. the Taylor development of P and Q converges on all points. To our knowledge, we designed the first algorithm to compute the singularities of a singular analytic curve defined as the projection of a smooth real analytic curve.

We designed the first algorithm to isolate the singularities of a restricted class of analytic singular curves.

The work on curves took longer than expected, but the results were beyond our expectations, with the help of a post-doctoral student hired with the funding of the ANR. Moreover, we now have a better idea on how to handle 3D singular surfaces defined as the projection in (x,y,z) of 4D smooth surfaces implicitly defined by P(x,y,z,t) = Q(x,y,z,t) = 0. The results we got on analytic functions is also very encouraging. In particular, this could allow us to describe accurately robotic manipulators such as the 3-RRR for which no exact description exists in the state-of-the-art literature. On the implementation part, our tools are developed partly in python and partly in C++. This will allow us to include easily our future visualization library in the sage computer algebra system. If we find the time and the resources to do so, we will port all our tools in C/C++ to let them be more easily included in other computer algebra systems.

Our work lead to two articles submitted respectively in an international journal and an international conference listed below. Moreover, we wrote a prototype implementation in python and C++ to isolate the singular points of the projection of a smooth algebraic curve.

[1] R. Imbach, G. Moroz, M. Pouget. Numeric certified algorithm for the topology of resultant and discriminant curves, submitted to Journal of Symbolic Computation.

[2] R. Imbach, G. Moroz, M. Pouget. Numeric and Certified Isolation of the Singularities of the Projection of a Smooth Space Curve, submitted to MACIS 2015.

Many applications in scientific computing can be modeled via polynomial systems possibly with parameters. Most information about the initial problem is thus encoded in the solution set of such systems. In the simplest examples, the solutions are a finite set of points, but to model more complex applications, more variables and constraints are needed and the set of solutions can be a curve, a surface or an even higher dimensional object. Some applications, such as robotics or visualization, require a description of the solution set with guarantees. One can distinguish two types of guarantees: topological, all the components and all the singularities (isolated points or self-intersections) must be reported; geometrical, the solution set must be approximated within a given distance.

Theoretically, symbolic methods from computer algebra can guarantee the topology of any polynomial system via resultants, Gröbner basis or Cylindrical algebraic decomposition. However, the high complexity of these purely algebraic methods prevents them to be applied in practice on difficult instances. On the other hand, purely numerical methods such as interval arithmetic or subdivision are efficient in practice for non-singular set, but are lacking topological guarantees near singular points. This issue is a long-time challenge in the community of numerical computation.

This exposition of the strengths and weaknesses of symbolic/numeric methods advocates for a new trend of work combining symbolic and numeric methods together. The objective of our project is to intertwine further symbolic/numeric approaches to compute efficiently solution sets of polynomial systems with TOPOLOGICAL and geometrical guarantees in the SINGULAR case. Technically, we will explore the use of local algebraic properties (local rings at singularities) and interval arithmetic (Krawczyk operator) to isolate singularities. Currently, certifying the topology around one singular point requires the certification of the topology around all singular points (e.g. homotopy methods) or the usage of non-practical separation bounds (e.g. subdivision). Our new singular certification criteria will be local and will naturally improve algorithms based on subdivision and algorithms based on path tracking. We are aware of the a priori high complexity of the worst-case scenario for general polynomial systems. Hence, instead of working on general systems, one objective is to identify classes of problems with restricted types of singularities and develop dedicated methods that take advantage of the structure of the associated polynomial systems. We focus on two applications: the visualization of algebraic curves and surfaces and the mechanical design of robots. We plan to extend the class of manipulators that can be analyzed, and the class of algebraic curves and surfaces that can be visualized with certification.

The partners of the project are selected for the complementarity of their expertises. Guillaume Moroz is an expert of computer algebra and developed the Maple package RootFinding[Parametric] and specific tools for robotics (ANR SIROPA 2007-2011). Marc Pouget is an expert of topology and geometry of curves and surfaces and developed visualization software (CGAL and Isotop). G. Moroz and M. Pouget are both in the INRIA VEGAS team, G. Moroz is new in the team and strengthens the non-linear computational geometry theme of VEGAS. We also have two teams of external collaborators. Joris Van Der Hoven and Grégoire Lecerf are experts in numerical and symbolic computations and computer algebra systems (Mathemagix). Finally, Philippe Wenger and Damien Chablat, from the robotic team at IRCCyN, who work on the mechanical design of manipulators will validate our methods with our prototype implementations.

Project coordinator

Monsieur Guillaume MOROZ (INRIA Nancy Grand Est)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

INRIA NGE INRIA Nancy Grand Est

Help of the ANR 96,652 euros
Beginning and duration of the scientific project: February 2014 - 42 Months

Useful links

Sign up for the latest news:
Subscribe to our newsletter