## Günter Rote, Francisco Santos, and Ileana Streinu:

# Expansive motions and the polytope of pointed pseudo-triangulations

In: *Discrete and Computational Geometry—The Goodman–Pollack
Festschrift.* Editors: Boris Aronov, Saugata Basu, János
Pach, and Micha Sharir, Algorithms and Combinatorics, vol. 25,
Springer Verlag, Berlin 2003, pp. 699–736.
doi:10.1007/978-3-642-55566-4_33,
arXiv:math/0206027 [math.CO].
### Abstract

We introduce the polytope of pointed pseudo-triangulations of a point set in
the plane, defined as the polytope of infinitesimal expansive motions of the
points subject to certain constraints on the increase of their distances. Its
1-skeleton is the graph whose vertices are the pointed pseudo-triangulations of
the point set and whose edges are flips of interior pseudo-triangulation
edges.

For points in convex position we obtain a new realization of the
associahedron, i.e., a geometric representation of the set of
triangulations of
an `n`-gon, or of the set of binary trees on `n` vertices, or of many other
combinatorial objects that are counted by the Catalan numbers. By
considering
the 1-dimensional version of the polytope of constrained expansive
motions we
obtain a second distinct realization of the associahedron as a
perturbation of
the positive cell in a Coxeter arrangement.

Our methods produce as a by-product a new proof that every simple
polygon or
polygonal arc in the plane has expansive motions, a key step in the
proofs
of the Carpenter's Rule Theorem by Connelly,
Demaine and Rote (2000) and by
Streinu (2000).

Last update: October 13, 2003.