Kanj, Iyad ;
Xia, Ge
Flip Distance Is in FPT Time O(n+ k * c^k)
Abstract
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 \mathbb{N}. It is a fundamental and a challenging problem.
In this paper we present an algorithm for the Flip Distance problem that
runs in time O(n + k \cdot c^{k}), for a constant c \leq 2 \cdot
14^11, which implies that the problem is fixedparameter tractable. The
NPhardness reduction for the Flip Distance problem given by Lubiw
and Pathak can be used to show that, unless the exponentialtime 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.
BibTeX  Entry
@InProceedings{kanj_et_al:LIPIcs:2015:4937,
author = {Iyad Kanj and Ge Xia},
title = {{Flip Distance Is in FPT Time O(n+ k * c^k)}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {500512},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897781},
ISSN = {18688969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4937},
URN = {urn:nbn:de:0030drops49371},
doi = {10.4230/LIPIcs.STACS.2015.500},
annote = {Keywords: triangulations, flip distance, parameterized algorithms}
}
26.02.2015
Keywords: 

triangulations, flip distance, parameterized algorithms 
Seminar: 

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Issue date: 

2015 
Date of publication: 

26.02.2015 