Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

A POINT SET WHOSE SPACE OF TRIANGULATIONS IS DISCONNECTED. 2


A point set whose space of triangulations is disconnected

Francisco Santos, Universidad de Cantabria

Let ${\cal A}$ be a finite point set in the Euclidean space of a certain dimension. By the ``space of triangulations" of ${\cal A}$ we mean either of the following two objects: the poset of all polyhedral subdivisions of ${\cal A}$(the so-called Baues poset of ${\cal A}$, see e.g. lecture 9 in [7]) considered as an abstract simplicial complex in the standard way [1]; or the graph of triangulations of ${\cal A}$, whose vertices are the triangulations of ${\cal A}$ and whose edges are the geometric bistellar operations between (``flips'') them, see e.g. [3].

We construct a point configuration in dimension 6 and a triangulation of it which admits no geometric bistellar operations. This means that this triangulation is an isolated element in both the Baues poset and the graph of triangulations of ${\cal A}$. The point configuration is the product ${\cal A}_1\times {\cal A}_2$ of two point configurations ${\cal A}_1$ of dimension four with 81 points and ${\cal A}_2$ of dimension two with four elements. The triangulation is a refinement of the product ${\cal T}_1\times {\cal T}_2$ of respective triangulations of ${\cal A}_1$ and ${\cal A}_2$, based on the idea of ``staircase triangulations" of the product of two simplices, see [4] page 282.

Our example answers in the negative the generalized Baues question for triangulations, which asked whether the Baues poset of every point configuration has the homotopy type of a sphere of a certain dimension (see [5]). It also solves one of the ``challenges" in [8] and has potential impact not only in discrete and computational geometry but also in algebraic geometry, via the close relation between subdivisions of polytopes and toric varieties (see, e.g. [2]).

The construction is based in several respects (some obvious, some not) on the paper [6]. A draft containing all the details and proofs is available upon request to the author.


 
Theoretical Computer Science Back