I have this problem.
Let $a$ and $b$ two horizontal lines in the plane and a set $S$ of $n$ points distributed half in each one of them. All possible triangles use two points from $a$ and one from $b$ or two points from $b$ and one from $a$.
I need to prove that the numbers of flips necessary to reach a Delaunay triangulation from a given triangulation could be quadratic.
Any help, suggestion or a link where to find related information would be apreciated.
Let $n=2m$. Any such triangulation will have $2(m-1)$ triangles; $m-1$ triangles have their base on the lower line, and the other half have their base on the top line. Number the triangles whose base is on the lower line $1$ to $m-1$ from left to right, and number the points on the top line $1$ to $m$ from left to right. Let $p_i$ be the top point of the $i^{th}$ lower triangle. The vector $(p_1,p_2,\dots,p_{n-1})$ determines the triangulation, and satisfies $$ p_1\le p_2\le \dots\le p_n $$ Any such sequence of numbers satisfying these inequalities is the vector of a triangulation. Importantly, performing a flip only changes one of these coordinates by $\pm1$.
Now, let $T_1$ be the triangulation $(1,1,\dots,1)$, and let $T_2$ be $(m,m,\dots,m)$. It takes $(m-1)^2$ flips to get from $T_1$ to $T_2$. Finally, let $T_D$ be the Delaunay triangulation. By the triangle inequality, the maximum flip distance from $T_D$ to either $T_1$ or $T_2$ is at least $\frac12(m-1)^2$.