Expansive Motions and the Polytope of Pointed Pseudo-Triangulations

Details Expansive Motions and the Polytope of Pointed Pseudo-Triangulations Expansive Motions and the Polytope of Pointed Pseudo-Triangulations

2002-06-04

arxiv.org/abs/math/0206027v2

In "Discrete and Computational Geometry - The Goodman-Pollack Festschrift" (B. Aronov et al., eds), Springer Verlag, 2003, pp.

Mathematics

Combinatorics

40 pages, 7 figures. Changes from v1: added some comments (specially to the "Further remarks" in Section 5) + changed to final

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

Expansive Motions and the Polytope of Pointed Pseudo-Triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Expansive Motions and the Polytope of Pointed Pseudo-Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Expansive Motions and the Polytope of Pointed Pseudo-Triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-96164