[home] -
[up]
Fall 2001: Discrete Geometry |
Program |
Preliminary abstracts for the lectures:
- Jack
Snoeyink (UNC at Chapel Hill):
Pseudo-triangulations in the plane
Algorithms that perform computations on sets of points, segments, or
polygons in the plane frequently benefit from using the points to decompose
the plane into simpler regions: triangulations, Voronoi diagrams, visibility
maps, and Delaunay tesselations are good examples. Decompositions called
pseudo-triangulations (or geodesic triangulations) have recently been
studied because of their applications to visibility, ray shooting, kinetic
collision detection, and rigidity. This talk will survey several results in
these areas and point out open problems.
- Jürgen Richter-Gebert (TU München) :
Minimal and maximal triangulations
Triangulations with extremal properties (like having a minimal/maximal
number of simplices, having simplices with large dihedral angles,
etc.) are very often ``objects of desire'' in theory and applications.
We will study the computational complexity of computing triangulations
with such extermal properties. In particular, we will learn that it
is in general difficult (NP-hard) to compute them. We will also see
that different variations on the definition of admissible
triangulations very much influence the minimal number of simplices
that are required for a triangulation. In particular there are
polytopes that require a quadratic number of simplices for a
triangulation, however if one allows to introduce additional interior
points a linear number suffices. The general spirit of the lectures
will be to learn about several ``tricks'' and ``gadgets'' that, if combined
in the right way, can be used as a kind of construction kit for
producing such results.
- Jörg Rambau
(ZIB Berlin):
Triangulations of cyclic polytopes:
A friendly world with no limits on the (co-)dimension
Every two triangulations of a two-dimensional convex polygon can
be transformed into each other by means of edge flips, i.e.,
removing the edge in some quadrilateral and inserting the other
possible diagonal. Cyclic polytopes can be seen as
generalizations of convex polygons to higher dimensions.
Moreover, there is also a generalization of edge flips to flips
in arbitrary dimensions. So we may ask whether any two
triangulations of a cyclic polytope can also be transformed into
each other by means of flips.
In this lecture, we study the beautiful combinatorial properties
of cyclic polytopes and their triangulations that - among other
things - enable us to answer this question.
- Emo Welzl
(ETH Zürich):
Discrete geometry under the Gale transform
Gale diagrams and the Gale transform were developed
by Micha Perles in the sixties of the previous century.
This duality theory reveals a number of surprising relations
among several results in discrete geometry. For example,
given a finite set of points in the plane, we look at all
triples of points that form a triangle whose interior
contains the origin. How large can this number be for
n points? This question relates to the famous Upper
Bound Theorem for Polytopes through the Gale Transform
(and also to a simple basic question in stochastic
geometry). This is well-known, but recently a number
of new incarnations of the duality have been discovered,
notably some which exploit the Generalized Lower Bound
Theorem for Polytopes.
Moreover, if you have problems in envisioning a
10-dimensional polytope with 12 or 13 facets, we might
be able to provide some help.
- Günter
M. Ziegler (TU Berlin):
The g-theorem and related conjectures
We will look at results and conjectures about the
f-vectors of triangulations and subdivisions.
This will include very famous results such as the
g-Theorem for simplicial polytopes,
important open problems such as the g-conjectures
for simplicial spheres,
areas with substantial recent progress such as
the f-vectors of general 4-dimensional polytopes
and of 3-dimensional simplicial spheres, and
embarassing problems such as the upper bound
problems for triangulated simplices.
[home] -
[up] -
[top]
|
Last modified: Tue Sep 11 07:28:56 MEST 2001
ziegler@math.tu-berlin.de |