NoDI seminar

Towards Numerical Computational Geometry

Chee K. Yap 15:00, July 30, 2014 321 Main Building, Beihang University

Abstract: Exact Geometric Computation (EGC) has provided a powerful paradigm for correct implementation of geometric algorithms for two decades. It is the most successful technique in Computational Geometry, and has led to successful libraries (CGAL, LEDA, Core Library) and numerous practical robust algorithms. We have fairly good understanding of the key techniques and what can be achieved under this paradigm. We review some strong reasons to extend this paradigm:

  • The existence of exact solutions may not be known (e.g., analytic roots)
  • Exact methods may be too inefficient (e.g., shortest path amidst discs)
  • Exact algorithms may not be known (e.g., Voronoi diagram of polyhedra)
  • Exactness is inappropriate in many practical problems (e.g., robot motion planning)

To get around this, we can use the well-known idea of computing up to some epsilon resolution. But we will point out some problems with the standard use of the epsilon parameter. Our proposed solution is surprisingly new and opens up new classes of algorithms. The correct viewpoint is to develop "purely numerical" approaches. It is an exciting new direction for Computational Geometry: it will allow us to solve old problems more efficiently, and allow us to solve previously untouchable problems. We will illustrate with examples from several of our recent papers, including analytic root isolation, isotropic approximation of surfaces, robot motion planning.

Poster Slides Photos