MathDB

A convex

n

-vertex polygon is partitioned into triangles by nonintersecting diagonals . The following operation, called perestroyka (=reconstruction) , is allowed: two triangles

ABD

and

BCD

with a common side may be replaced by the triangles

ABC

and

ACD

. By

P(n)

denote the smallest number of perestroykas needed to transform any partitioning into any other one. Prove that (a)

P ( n ) \ge n - 3

(b)

P (n) \le 2n - 7

(c)

P(n) \le 2n - 10

n \ge 13

.
( D.Fomin , based on ideas of W. Thurston , D . Sleator, R. Tarjan)

Problem Statement