Robust Geometric Computation Minisymposium: ABSTRACTS

Christoph Hoffmann

On the Role of Exact Arithmetic in Geometric Computation

ABSTRACT: Exact arithmetic is emerging as final arbiter of uncertainty in geometric computations such as segment intersection, Delaunay triangulation, Voronoi diagrams, and many others. This creates a false sense of security in a world where even the input is in doubt. We discuss this trend and possible alternatives.

Mark Foskey

Fast and Accurate Computations with Algebraic Primitives and Predicates

ABSTRACT: Most of the work in accurate and robust geometric computations has been restricted to linear primitives. It is based on "exact computation paradigm" that uses rational arithmetic for the underlying computations. There is a general perception that extending "exact computation paradigm" to non-linear problems is impractical and very hard to implement. I describe some approaches for accurate evaluation of algebraic predicates, root isolation of polynomial systems, and exact manipulation of algebraic points and curves for geometric applications. The set of applications include boundary evaluation of low degree algebraic solids, medial axis computations, computing curve arrangements etc. Based on these algorithms, I will describe two libraries, MAPC and PRECISE, which can be used for different geometric applications. The next major challenge is to develop robust approaches to handle degeneracies.

Sylvain Pion

Solutions to robustness problems in CGAL

ABSTRACT: The CGAL library is a collection of geometric algorithms implemented in C++ in a generic way. This talk will describe how the well known non-robustness problems have influenced the design of the library, what are the actual solutions that we propose in order to solve these problems and what are their trade-offs in terms of efficiency, generality and ease of use.

Jonathan Richard Shewchuk

Making Roundoff Error Less Unbearable

ABSTRACT: Sometimes you don't have time -- running time or programming time -- to use exact arithmetic or other methods of achieving numerical robustness. Sometimes, luckily, the worst effects of floating-point roundouff can be alleviated by chooseing expressions wisely. I offer some advice on how to write less dangerous mathematical expressions for floating-point computation.

Chee Yap

Robust Geometric Computation for Everyone?

ABSTRACT: A large class of basic but important geometric computations can be achieved robustly and efficiently. Such computational problems include mesh-generation and low-degree algebraic problems. What is more important is that such techniques can be encoded into general purpose libraries so that any programmer can access these capabilities, without significant changes to their algorithms or code. There are basically two current libraries that offer this capability: LEDA_Real and our own Core Library. Both are C++-libraries, and any C++ programmer can write robust programs by calling these libraries. The underlying approach of these libraries is the Exact Geometric Computation (EGC) approach. We outline the major challenges ahead as we continue to develop the theory and technology of EGC.