Title

Support Functions and Non-Linear Computational Geometry

 Speakers

Franz Aurenhammer (Graz University of Technology, Austria)

Bert Juettler (Johannes Kepler University Linz, Austria)

 Abstract

Support functions are a classical tool in convex geometry. This tutorial provides an introduction to the support function representation of free-form curves and surfaces, and it discusses relevant applications from Geometric Computing and Computational Geometry. It consists if two parts. 

Part 1 is devoted to Curves and Surfaces with (Piecewise) Polynomial Suuport Functions. We will analyze the geometry of these curves and surfaces. In addition, several applications will be discussed. These include the computation of envelope surfaces of special surfaces, the generation of exact rational offsets for special classes of surfaces, such as quadratic triangular Bezier surface patches and of quadric surfaces, and the generation of three-valent meshes with planar faces. 

Part 2 shall discuss the use of support functions from the algorithmic viewpoint. In particular, we will focus in the class of piecewise circular objects. First we will show that the use of these objects offers significant computational advantages, e.g., for computing the medial axis of planar domains with free-form boundaries. Second, we will show that the use of support functions leads to conceptionally simple and computationally efficient algorithm for solving various problems, such as the computation of the convex hull of piecewise spherical objects.

Title

Overview on Delaunay and non-Delaunay longest edge based mesh generation and open problems

 Speaker

Maria-Cecilia Rivara (Department of Computer Science,  University of Chile)

 Abstract

Longest-edge based approach for mesh generation includes: (1) Lepp-bisection algorithms for triangulation refinement which produce sequences of nested (non-Delaunay) refined triangulations of analogous geometrical quality to the input triangulation, as needed for finite element applications, multigrid methods and multiresolution terrain applications; and (2) Lepp-Delaunay algorithms for the automatic construction of a quality Delaunay triangulation of complex geometrical objects as needed for obtaining an input mesh in finite element methods. In 2-dimensions, these algorithms proceed by iterative selection of a point M which is midpoint of a terminal edge (a longest edge for both triangles that share this edge) which is then inserted in the mesh either by longest edge bisection of the triangles that share the terminal edge, or by Delaunay insertion of M. The use the longest edge propagating path (Lepp) associated to a target processing triangle is used to determine a terminal edge in the current mesh. We review the mathematical properties of the longest edge bisection of triangles, a taxonomy of triangles obtained by longest edge bisection, and complexity analysis of the bisection process of an individual triangle. We discuss the goemetrical properties and implementation cost of the Lepp-bisection algorithms, as well as the special case of right triangle bintree algorithms for huge regular terrain data. We discuss Lepp-Delaunay algorithms, designed as a generalization of previous Lepp-bisection algorithms, for improving the smallest angles in a Delaunay triangulation. We study the geometrical properties of the Lepp-Delaunay algorithms, termination issues and optimal-size property. We discuss the generalization of some algorithms to 3-dimensions and the open problems that remain to be studied.