Title: Pre-Triangulations and Liftable Complexes

Speaker: Franz Aurenhammer
Institute for Theoretical Computer Science
Technische Universitaet Graz, Austria

Date: Monday, June 21, 2005 
Time 11-12 Venue: Room 3464, HKUST   


Abstract 
Polygonal complexes in the plane have been objects of interest in
combinatorial and computational geometry from various points of view.
Classical examples are line arrangements, Voronoi diagrams, and triangulations.
Whereas generalizations of line arrangements
and Voronoi diagrams meanwhile have been studied extensively, 
the discovery of a structure that generalizes triangulations 
but still retains their basic properties 
(e.g., planarity, simple face shape, and flippability)
happened more recently. In a so-called pseudo-triangulation,
faces bounded by three concave chains, rather than by three line
segments, are allowed. Pseudo-triangulations enjoy a variety
of combinatorial and geometric properties, and lead to efficient data
structures in many areas.

In this talk, we generalize triangulations further
-- in a natural way and to the utmost in a certain sense. 
We arrive at a concept we will call a pre-triangulation
in a given domain. Pre-triangulations arise in three different contexts:
In the characterization of complexes that are liftable
to three-space in a strong sense, in flip sequences for
general polygonal complexes, and as graphs of maximal locally convex
functions.