| B1:01 B1:02 B1:03 B1:04 B1:05 B1:06 B1:07 B1:08 B1:09 B1:10 B1:11 B1:12 B1:13 B1:14 B1:15 B1:16 B1:17 B1:18 B1:19 (2007) | |||||||||||||||
Abstract | |||||||||||||||
| We introduce the polytope of pointed pseudo-triangulations, defined as the polytope of expansive motions of a planar point set 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. Our polytopes have a large number of free parameters, leading to entire families of distinct representations. In particular, our associahedra are distinct from the other previously known realizations. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||