Document Open Access Logo

An Improved FPT Algorithm for the Flip Distance Problem

Authors Shaohua Li, Qilong Feng, Xiangzhong Meng, Jianxin Wang

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.65.pdf
  • Filesize: 0.54 MB
  • 13 pages

Document Identifiers

Author Details

Shaohua Li
Qilong Feng
Xiangzhong Meng
Jianxin Wang

Cite As Get BibTex

Shaohua Li, Qilong Feng, Xiangzhong Meng, and Jianxin Wang. An Improved FPT Algorithm for the Flip Distance Problem. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.65

Abstract

Given a set \cal P of points in the Euclidean plane and two triangulations of \cal P, the flip distance between these two triangulations is the minimum number of flips required to transform one triangulation into the other. The Parameterized Flip Distance problem is to decide if the flip distance between two given triangulations is equal to a given integer k. The previous best FPT algorithm runs in time O^*(k\cdot c^k) (c\leq 2\times 14^11), where each step has fourteen possible choices, and the length of the action sequence is bounded by 11k. By applying the backtracking strategy and analyzing the underlying property of the flip sequence, each step of our algorithm has only five possible choices. Based on an auxiliary graph G, we prove that the length of the action sequence for our algorithm is bounded by 2|G|. As a result, we present an FPT algorithm running in time O^*(k\cdot 32^k).

Subject Classification

Keywords
  • triangulation
  • flip distance
  • FPT algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Oswin Aichholzer, Ferran Hurtado, and Marc Noy. A lower bound on the number of triangulations of planar point sets. Computational Geometry, 29(2):135-145, 2004. URL: http://dx.doi.org/10.1016/j.comgeo.2004.02.003.
  2. Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz. Flip distance between triangulations of a simple polygon is NP-complete. Discrete & Computational Geometry, 54(2):368-389, 2015. URL: http://dx.doi.org/10.1007/s00454-015-9709-7.
  3. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Michael T. Hallett, and Harold T. Wareham. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences, 11(1):49-57, 1995. URL: http://dx.doi.org/10.1093/bioinformatics/11.1.49.
  4. Jianer Chen. Parameterized computation and complexity: A new approach dealing with np-hardness. J. Comput. Sci. Technol., 20(1):18-37, 2005. URL: http://dx.doi.org/10.1007/s11390-005-0003-7.
  5. Jianer Chen, Donald K. Friesen, Weijia Jia, and Iyad A. Kanj. Using nondeterminism to design efficient deterministic algorithms. Algorithmica, 40(2):83-97, 2004. URL: http://dx.doi.org/10.1007/s00453-004-1096-z.
  6. Jianer Chen, Chao Xu, and Jianxin Wang. Dealing with 4-variables by resolution: An improved maxsat algorithm. Theor. Comput. Sci., 670:33-44, 2017. URL: http://dx.doi.org/10.1016/j.tcs.2017.01.020.
  7. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  8. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS, Palm Springs, USA, pages 150-159, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  9. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discrete Math., 27(1):290-309, 2013. URL: http://dx.doi.org/10.1137/110843071.
  10. Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. Google Scholar
  11. Gerald E. Farin. Curves and surfaces for computer-aided geometric design - a practical guide (4. ed.). Computer science and scientific computing. Academic Press, 1997. Google Scholar
  12. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, Portland, USA, pages 142-151, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.10.
  13. Bernd Hamann. Modeling contours of trivariatc data. Mathematical Modeling and Numerical Analysis, 26:51-75, 1992. Google Scholar
  14. Ferran Hurtado, Marc Noy, and Jorge Urrutia. Flipping edges in triangulations. Discrete & Computational Geometry, 22(3):333-346, 1999. URL: http://dx.doi.org/10.1007/PL00009464.
  15. Iyad A. Kanj and Ge Xia. Flip Distance is in FPT time O(n+k⋅ c^k). In proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS, Garching, Germany, pages 500-512, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.500.
  16. Iyad A. Kanj and Ge Xia. Computing the flip distance between triangulations. to appear in Discrete & Computational Geometry, 2017. Google Scholar
  17. Charles L. Lawson. Transforming triangulations. Discrete Mathematics, 3(4):365-372, 1972. URL: http://dx.doi.org/10.1016/0012-365X(72)90093-3.
  18. Anna Lubiw and Vinayak Pathak. Flip distance between two triangulations of a point set is NP-complete. Computational Geometry, 49:17-23, 2015. URL: http://dx.doi.org/10.1016/j.comgeo.2014.11.001.
  19. Joan M. Lucas. An improved kernel size for rotation distance in binary trees. Information Processing Letters, 110(12-13):481-484, 2010. URL: http://dx.doi.org/10.1016/j.ipl.2010.04.022.
  20. Alexander Pilz. Flip distance between triangulations of a planar point set is APX-hard. Computational Geometry, 47(5):589-604, 2014. URL: http://dx.doi.org/10.1016/j.comgeo.2014.01.001.
  21. Larry L. Schumaker. Triangulations in CAGD. IEEE Computer Graphics and Applications, 13(1):47-52, 1993. URL: http://dx.doi.org/10.1109/38.180117.
  22. Feng Shi, Jianxin Wang, Yufei Yang, Qilong Feng, Weilong Li, and Jianer Chen. A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees. SCIENCE CHINA Information Sciences, 59(1):1-14, 2016. URL: http://dx.doi.org/10.1007/s11432-015-5355-1.
  23. Daniel D. Sleator, Robert E. Tarjan, and William P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC, Berkeley, USA, pages 122-135, 1986. URL: http://dx.doi.org/10.1145/12130.12143.
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 About DROPS Imprint Privacy Contact