TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 23.10.2014


Page Content

to Navigation

Flip Distance is in FPT time O(n+ k * c^k)

Prof. Iyad Kanj (DePaul University)

Let T be a triangulation of a set P of n points in the plane, and let e be an edge shared by two triangles in T such that the quadrilateral Q formed by these two triangles is convex. A flip of e is the operation of replacing e by the other diagonal of Q to obtain a new triangulation of P from T. The flip distance between two triangulations of P is the minimum number of flips needed to transform one triangulation into the other. The Flip Distance problem asks if the flip distance between two given triangulations of P is k, for some given k in N. It is a fundamental and a challenging problem whose complexity for the case of triangulations of a convex polygon remains open for over 25 years.

In this talk we present an algorithm for the Flip Distance problem that runs in time O(n + k * c^k), for a constant c <= 2 * 14^11, which implies that the problem is fixed-parameter tractable. The NP-hardness reduction for the Flip Distance problem given by Lubiw and Pathak can be used to show that, unless the exponential-time hypothesis (ETH) fails, the Flip Distance problem cannot be solved in time O*(2^{o(k)}). Therefore, one cannot expect an asymptotic improvement in the exponent of the running time of our algorithm.

Iyad Kanj
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe