License:
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.44
URN: urn:nbn:de:0030-drops-176965
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17696/
Li, Haohong ;
Xia, Ge
An ?(3.82^k) Time FPT Algorithm for Convex Flip Distance
Abstract
Let P be a convex polygon in the plane, and let T be a triangulation of P. An edge e in T is called a diagonal if it is shared by two triangles in T. A flip of a diagonal e is the operation of removing e and adding the opposite diagonal of the resulting quadrilateral 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 Convex Flip Distance problem asks if the flip distance between two given triangulations of P is at most k, for some given parameter k ∈ ℕ.
We present an FPT algorithm for the Convex Flip Distance problem that runs in time ?(3.82^k) and uses polynomial space, where k is the number of flips. This algorithm significantly improves the previous best FPT algorithms for the problem.
BibTeX - Entry
@InProceedings{li_et_al:LIPIcs.STACS.2023.44,
author = {Li, Haohong and Xia, Ge},
title = {{An ?(3.82^k) Time FPT Algorithm for Convex Flip Distance}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {44:1--44:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-266-2},
ISSN = {1868-8969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17696},
URN = {urn:nbn:de:0030-drops-176965},
doi = {10.4230/LIPIcs.STACS.2023.44},
annote = {Keywords: Flip distance, Rotation distance, Triangulations, Exact algorithms, Parameterized complexity}
}
Keywords: |
|
Flip distance, Rotation distance, Triangulations, Exact algorithms, Parameterized complexity |
Collection: |
|
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
03.03.2023 |