# Quadratic number of flips to Delaunay triangulation

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