| ||
So far, we have discussed several ways to address the problems of degeneracy and robustness in geometric computing. Now, we will try to categorize the given ideas and list their advantages and disadvantages. Additionally, we will give an overview of existing software packages and libraries. Practitioners may decide whether their implementation should be supported by one of the given libraries.
First, we can subdivide an algorithmic solution by imprecise or precise arithmetic usage. A precise arithmetic algorithm follows the idea of perfect arithmetic in the Real RAM model (see Section 9.3), whereas an imprecise algorithm is implemented with imprecise arithmetic, for example floating-point arithmetic (see Section 9.6).
The imprecise arithmetic approach has the following advantages:
by construction, robustness and degeneracy problems do not exist;
standard predicates and standard algorithms can be adapted easily.
Disadvantages of the imprecise arithmetic approach include:
increasing time complexity;
new inventions beyond standard predicates and algorithms necessary;
reinvention of computational geometry;
probably no standard libraries and software packages available.
The precise arithmetic approach has the following advantages:
the Real RAM model allows perfect design and analysis;
investment of more than 20 years of researcher and developer experience;
many efficient solutions for many geometric problems;
standard libraries and software packages available.
Disadvantages of the precise arithmetic approach include:
the Real RAM is a theoretical model and actually not implementable;
degeneracy and robustness must be solved additionally.
Going on with Real RAM algorithms, we can further subdivide geometric algorithms by whether or not they support the EGC paradigm. The main feature in the EGC agreement is that the combinatorial computation of an algorithm is driven by geometric predicates only. EGC assumes exact predicate evaluation (due to the Real RAM), so that independently from the choice of the (exact) arithmetic, the combinatorial result is always the same. Some additional non-combinatorial results may vary with respect to the given arithmetic. See Section 9.3.4, [Yap 93], and [Yap and Dub 95].
Non-EGC algorithms have the following advantages:
no limitations for the design and analysis of algorithms;
represent a bigger class of problems and algorithms.
Disadvantages of non-EGC algorithms include:
no standardization of algorithms;
non-flexible against the exchange of arithmetic;
degeneracy and robustness problems must be solved internally;
probably combinatorics and computations are not separated.
EGC algorithms have the following advantages:
predicate-driven algorithms;
standardization of algorithms;
robustness and degeneracy problems are solved by definition;
flexible arithmetic exchange;
standardization of libraries and software packages;
partition into the combinatorial and the computational part of the problem.
Disadvantages of EGC algorithms include:
limited to a subclass of problems and algorithms;
combinatorial and computational part may be separated artificially;
shifts problems to the arithmetic packages;
does not support direct solutions for degeneracy.
Exact arithmetic for EGC can be achieved by many methods . We can distinguish between multi-precision and restricted-precision arithmetic. If the input and output are small, restricted-precision arithmetic or adaptive restricted-precision arithmetic is sufficient and fast. Otherwise, one has to choose a multi-precision package, which will increase the running time.
Computer algebra systems solve a lot of arithmetic problems efficiently . But they are designed for a more general purpose and come along with general data structures. Additionally, computer algebra systems are used in an interpreter modus and are slow against compiled solution. Finally, one has to pay for them.
General big-number packages are mainly free and they are more efficient either. Unfortunately, they are not designed solely for geometric problems. Therefore, speed-up techniques such as lazy arithmetic or floating-point filters are not implemented.
Specially designed computational geometry arithmetic packages are more efficient. The free Core Library, the free Real/Expr library, and the commercial LEDA version support the EGC paradigm by the design of geometric predicates. These three systems also support the efficient evaluation of determinants . The data type leda real of LEDA is made faster by lazy arithmetic, floating-point filters, and separation bounds; see Section 9.3.3. The Core Library has incorporated several separation bounds, as well [Li 01]. LiDIA and LEDA additionally contain some geometric data structures, and in LEDA, some efficient geometric algorithms are implemented. LEA is a lazy arithmetic floating-point library. All computational geometry arithmetic libraries are implemented in C++.
Arithmetic approaches for EGC. Restricted precision arithmetic includes:
non-adaptive arithmetic: standard arithmetic of programming languages (Integer/Rationals);
adaptive arithmetic: p -bit floating-point expansions; see Section 9.3.3;
adaptive usage of a multi-precision arithmetic supported by many multi-precision arithmetics.
Multi-precision arithmetic includes:
computer algebra systems
Maple
Mathematica
Scratchpad
Macsyma
general arithmetic C++ libraries
BigNum [Serpette et al. 89]
GMP, http://www.swox.com/gmp/ [Granlund 96]
PARI/GP, http://pari.math.u-bordeaux.fr/ [Batut et al. 00]
Some other free sources for numerical computations are listed at http://cliodhna.cop.uop.edu/~hetrick/c-sources.html
computational geometry arithmetic libraries
Real/Expr, http://www.cs.nyu.edu/exact/realexpr/ [Ouchi 97]
LEA [Benouamer et al. 93, Michelucci and Moreau 97]
LEDA, http://www.algorithmic-solutions.com [Mehlhorn and Nher 00]
LiDIA, http://www.informatik.tu-darmstadt.de/TI/LiDIA/
Core Library, http://www.cs.nyu.edu/exact/core/ [Karamcheti et al. 99a, Karamcheti et al. 99b]
Software packages. Finally, there are special software packages that contain data structures and algorithms. They also support the visualization and animation of the results up to some extent.
Computational geometry data structures and algorithms libraries include:
Computational Geometry Algorithms Library (CGAL)
[Fabri et al. 00]
http://www.cgal.org/
implemented in C++
supports EGC
contains a lot of algorithms and data structures
free software
revision 3.1 incorporates GMP and CORE Library
external visualisation components can be used
implemented and supported by researchers and developers
up-to-date software
Java Data Structures Library (JDSL)
[Tamassia et al. 97, Gelfand et al. 98, Goodrich and Tamassia 98, Baker et al. 99]
http://www.cs.brown.edu/cgc/jdsl/
contains GeomLib, a library for geometric applications
implemented in Java
implemented and supported by researchers and developers
mainly graph algorithms are implemented
focus is also on visualizations
free software
up-to-date software
XYZ Geombench
[Nievergelt et al. 91, Schorn 90]
http://www.schorn.ch/geobench/XYZGeoBench.html
implemented in Object Pascal
implemented and supported by researchers and developers
some classical computational geometry algorithms are implemented
intended to support animations
free software
no longer supported
GeoLab
[de Rezende and Jacometti 93a, de Rezende and Jacometti 93b]
http://www.cs.sunysb.edu/ algorith/implement/geolab/implement.shtml
implemented in C++
implemented and supported by researchers and developers
some classic computational geometry algorithms are implemented
intended to support animations
free software
makes use of the XView graphics library
In summary, we highly recommend using the EGC paradigm and the CGAL library for the design of geometric algorithms. The CGAL library is well supported and contains many geometric algorithms. Practitioners can easily extend the given framework of CGAL for their own implementations . It remains to choose an appropriate supporting arithmetic package for CGAL. LEDA itself contains additional geometric data structures and algorithms, and runs well with CGAL. Unfortunately, LEDA is not available for free. Therefore, we recommend using the EGC-supporting Core Library or one of the general multi-precision arithmetic packages, for example GNU MP. Fortunately, in the latest version of CGAL, version 3.1, GNU MP and the Core Library are already incorporated.