1 Search Results for "Li, Haohong"

Document
DOI: 10.4230/LIPIcs.STACS.2023.44
An 𝒪(3.82^k) Time FPT Algorithm for Convex Flip Distance

Authors: Haohong Li and Ge Xia

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

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.
Cite as

Haohong Li and Ge Xia. An 𝒪(3.82^k) Time FPT Algorithm for Convex Flip Distance. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.44},
  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}
}
  • Refine by Author
  • 1 Li, Haohong
  • 1 Xia, Ge

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Exact algorithms
  • 1 Flip distance
  • 1 Parameterized complexity
  • 1 Rotation distance
  • 1 Triangulations

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact