VEGAS VEGAS VEGAS
Direct link to servers QI and ISOTOP

QI

QI stands for Quadrics Intersection. QI is the first exact, robust and efficient implementation of an algorithm for parameterizing the intersection of two arbitrary quadrics given in implicit form. QI computes an exact parameterization of the intersection of two quadrics with integer coefficients of arbitrary size with the following features:

  • QI identifies, separates and parameterizes all the algebraic components (lines, conics, cubic, quartic) of the intersection;
  • the parameterization is rational when one exists; otherwise the intersection is a non-singular quartic and the parameterization involves the square root of a polynomial;
  • the coefficients of parameterization are small in the sense that the degree of the field extension (over the rationals) on which they are defined is minimal except in a small number of cases in which they may involve one extra possibly unnecessary square root;
  • QI is fast and efficient and can routinely compute parameterizations of the intersection of quadrics with input coefficients having ten digits in less than 50 milliseconds on a mainstream PC.

ISOTOP

Isotop is a Maple software for computing the topology/isotopy of an implicit algebraic plane curve, that is, for computing an arrangement of polylines isotopic to the input curve. It also provides a new solution to the important problem of plotting such curves in a certified way, that is -- in particular -- without missing connected components, singular points, etc. This problem is also a necessary key step for computing arrangements of algebraic curves.

CGAL

CGAL is an open source software project that provides easy access to efficient and reliable geometric algorithms in the form of the C++ library CGAL, Computational Geometry Algorithms Library.

CGAL univariate Algebraic Kernel
Solving univariate polynomials and multivariate polynomial systems is critical in geometric computing with curved objects. Moreover, the real roots need to be isolated in a certified way in order to avoid possible inconsistency in geometric algorithms. We developed a C++ CGAL algebraic kernel for handling univariate polynomials based on the RS software developed in the INRIA Salsa team. This kernel consists of about 11,000 lines of source code.

Visqueux

Visqueux stands for Visibility Skeleton. It is a C++ software, still under development, for computing the visibility skeleton of polyhedra. It consists of about 27,000 lines. It currently computes, robustly, the vertices of the visibility skeleton of a set of disjoint convex polyhedra in generic position, that is the set of maximal free line segments tangent to four polyhedra. This development is a proof of concept of the algorithms developed in [Goaoc, 2004] and [Bronnimann et al., 2007]. It already allowed us to present an experimental study of the expected size of such 3D visibility global data structures in a random setting and, in particular, to show that the constant involved in the asymptotic complexity is small [Zhang et al., 2008].