Exact Geometric Computation

Exact Geometric Computation (EGC for short) to emphasize that the “exactness” is in the geometry, not in the arithmetic. EGC is the most successful approach in this informal sense: any problem that has been successfully treated by other approaches can also be treated using EGC, but EGC has done more. Moreover, the EGC solution is often more general and has better properties (since the underlying Euclidean geometry is preserved).
EGC thereby guarantees that the combinatorial output of the algorithm is the exact one. Two important computational consequences follow:
(1) EGC is computationally feasible. EGC avoids two infeasibility traps. First, it avoids the infeasibility of the consistency approach: by ensuring the combinatorial output is exact, we achieve consistency without having to do theorem
proving. Second, it avoids the infeasibility of naive numerical exactness: we only need to compute to sufficient precision to make the correct predicate evaluation. This adaptive complexity is vital in practice.
(2) It is possible to create a software EGC library whereby programmers can write robust programs just by calling the library to perform their arithmetic. For a large class of problems, such an EGC library is a “general solution”, as opposed to being a problem-specific or algorithm-specific solution. This
contrasts with many geometric approaches, or the earlier work in EGC which offer problem-specific solutions.
The Challenges Ahead. EGC is in the midst of an exciting development that seemed quite remote 10 years ago. It has emerged as the dominant approach to non-robustness. Using EGC libraries, programmers can now routinely write completely robust and reasonably efficient geometric code for a
large class of problems. Both LEDA and CGAL have been commercialized and used in industrial applications. For the rational bounded-depth class of problems, the consensus is that their nonrobustness problems have essentially been solved (in theory if not in practice). Such problems include convex hulls of points, mesh generation and polyhedral Boolean operations. But what lies
1. The perennial challenge of efficiency for EGC is currently focused on high degree algebraic computation. Such computations as found in CAD applications remain a severe challenge, as all current CAD software are nonrobust.
2. When EGC algorithms are embedded in larger application systems (such as a mesh generation system), we need to cascade the output of one algorithm as input to another algorithm. As the output of an EGC algorithm may be in high precision, it is desirable to reduce this precision in the cascade.

, , ,

  1. #1 by Sandeep on October 11, 2011 - 5:56 pm

    good analysis on geometric computation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: