max planck institut
informatik

Exacus web demo is a web-based application with Macromedia Flash client interface which allows to compute and visualize exact 2D arrangements of implicit real algebraic curves. We also provide various arrangement data, such as: number of arcs, vertices, isolated vertices and facets. Feature selection mode allows to emphasize on certain arrangement items, i.e., arcs, vertices or facets. It can be used for demonstrative and educational purposes.

What is Exacus ?

Exacus stands for Efficient and Exact Algorithms for Curves and Surfaces. This is Open Source software consisting of a set of C++ libraries designed following a generic programming paradigm widely known from STL. Our development experience rests upon Cgal and Leda libraries.

The main goal of Exacus project is to provide efficient, exact (in mathematical sense) and complete (handling highly degenerate cases) algorithms and implementations for various-degree non-linear geometry. With the help of our software one can compute arrangements of arbitrary-degree algebraic curves and curve arcs in the plane and quadrics in space. We also support boolean operations on polygons bounded by such curve arcs. Our algorithms can handle all degeneracies, such as singularities and intersections of high multiplicity; efficiency is guaranteed by making use of various filter techniques to avoid symbolic computations in many cases (modular filters, floating point filters) and special handling for fixed-degree algebraic curves. Currently the work is underway to extend arrangements computation to the curves embedded on a two-dimensional parametric surface.

In the near future Exacus is planned to become a part of Cgal project. The table below depicts a high-level structure of Exacus in the current state of development. The top-level libraries (ConiX, CubiX, QuadriX and AlciX) provide curve and curve pair analyses of conics, cubics, projected quadrics and arbitrary-degree algebraic curves respectively. SweepX layer serves as a generic interface for arrangement computations, using one of the top-level libraries. NumeriX provides algebraic foundations for computations with generic number types and polynomials. On the bottom level there are third-party libraries which provide various data structures, exact number types, graphic output, etc. Currently, some parts of NumeriX and SweepX layers are removed from Exacus, and instead integrated into the Cgal library.

ConiX (CnX)	CubiX (CbX)	QuadriX (QdX)	AlciX (AcX)
SweepX (SoX)
NumeriX (NiX)
Cgal library support
Boost Gmp Core Ntl Leda Qt

Arrangements of algebraic curves are treated by us in a three-step approach:

1. Segmentation of each input curve into a list of x-monotone segments [1]. This step consists of analysis topological and geometrical properties of an algebraic curve, using a symbolic-numerical lifting method. The output of the analysis is equivalent to the computation of a cylindrical algebraic decomposition with adjacency information.
   
   
2. Arrangement computation of the curve segments [2]. For that step, we use the generic sweep-line based implementation from the Arrangement package of CGAL. We provide a model for it that can handle algebraic curves of any degree. For that, we have efficient methods to analyze a single curve (see previous item), and a pair of algebraic curves. To translate these analyses into geometric predicates on the curve segments, we use the GAPS/SweepX library ([4]).
   
   
3. Plotting arcs of an arrangement [3]. Each curve arc is traced separetely in both directions starting from a seed point. In order to distinguish closely located features of the curves we employ local space subdivision. Robustness of our algorithm is guaranteed by three levels of increasing arithemtic precision (floating-point filtering).

All three subalgorithms guarantee the correctness of their results, so the resulting plot gives a mathematically true picture of the arrangement.

References:

1. Arno Eigenwillig, Michael Kerber, Nicola Wolpert: Fast and Exact Geometric Analysis of Real Algebraic Plane Curves. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC 2007), pp. 151-158.


2. Arno Eigenwillig, Michael Kerber: Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008) (to appear)


3. Pavel Emeliyanenko: Visualization of Points and Segments of Real Algebraic Plane Curves. Master thesis, Saarbrücken, Germany 2007


4. Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Lutz Kettner, Kurt Mehlhorn, Jocahim Reichel, Susanne Schmitt, Elmar Schömer, Nicola Wolpert: EXACUS: Efficient and exact algorithms for curves and surfaces. 13th Annual European Symposium on Algorithms (ESA 2005), LNCS 3669, 155-166.

---