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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.