9.7. Practical Recommendations and Existing Packages

9.7. Practical Recommendations and Existing Packages

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.

9.7.1. Imprecise and Precise Arithmetic

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.

9.7.2. Support for EGC

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.

9.7.3. Software Packages and Libraries

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.



Geometric Data Structures for Computer Graphics2006
Geometric Data Structures for Computer Graphics2006
ISBN: N/A
EAN: N/A
Year: 2005
Pages: 69

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net