Francisco Santos - Universidad de Cantabria

Small point sets with disconnected space of triangulations

Abstract: By the "space of triangulations of a point set" A I mean the graph whose vertices are the triangulations of A and whose edges correspond to bistellar flips between them. This graph is known to be connected in dimension 2, but the question in dimensions 3 and 4 is open.

Three years ago I constructed the first example of a point set with disconnected space of triangulations, with dimension 6 and more than 300 points. I am now presenting much smaller examples (dimension 5 and size 25-50) which, moreover, have the following features:

• they are much simpler to describe, not only due to their size but also because of their amount of symmetries. For example, one of the point sets is (essentially) the product of a 24-cell and a segment.
• the proof of disconnectedness relies on more elementary properties of triangulations and flips. In particular, I intend to give a self-contained proof in this talk.
• the examples can be moved into convex position, producing 5-dimensional polytopes with disconnected space of triangulations.
• the examples have unimodular triangulations, which imply that certain algebraic object called the Toric Hilbert Scheme of the point set is disconnected too.

The talk will be self-contained, starting with the definition and examples of bistellar flips and reviewing some previous results.

Colloquium - 16:00

Britta Broser - Freie Universität Berlin

Complex Tracing

Abstract: In the context of the geometry software Cinderella you can find interesting open problems concerning complexity theory and geometry. Here, geometric constructions are represented by Geometric Straight-Line Programs (GSP). They consist of free points and dependent elements (like the line connecting two points or one of the two angular bisectors of two intersecting lines). An instance of a GSP is an assignment of fixed values to all free parameters and choices.

A typical situation arising in Cinderella is the following: Given is an instance of a GSP (e.g. a drawing constructed by the user) and a continuous motion of the free points (e.g. the user drags one of the free points with the mouse). Then the software has to draw the "right" final instance after the motion. This problem is called tracing problem and it is known that it is a NP-hard.

Sometimes, for example for avoiding singularities, it might be useful to consider complex paths. But in contrast to the real situation, the complexity of complex tracing is still unknown.

In my talk, I want to formalize the setting described above and to give a quick overview about some future work.