## 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

Let be a finite point set in the Euclidean space of a certain dimension. By the space of triangulations" of we mean either of the following two objects: the poset of all polyhedral subdivisions of (the so-called Baues poset of , see e.g. lecture 9 in [7]) considered as an abstract simplicial complex in the standard way [1]; or the graph of triangulations of , whose vertices are the triangulations of 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 . The point configuration is the product of two point configurations of dimension four with 81 points and of dimension two with four elements. The triangulation is a refinement of the product of respective triangulations of and , 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]).