Back
Bosch-Calvo_2023_Else_ipl
Journal article

An improved kernel for the flip distance problem on simple convex polygons

  • Bosch-Calvo, Miguel ORCID Istituto Dalle Molle di studi sull'intelligenza artificiale (IDSIA), Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera ; Department of Data Science and Engineering, Maastricht University, the Netherlands
  • Kelk, Steven Department of Data Science and Engineering, Maastricht University, the Netherlands
  • 2023
Published in:
  • Information processing letters. - 2023, vol. 182, p. 106381
Algorithms
Parameterized complexity
Kernel
Triangulation
Simple convex polygons
English The complexity of computing the flip distance between two triangulations of a simple convex polygon is unknown. Here we approach the problem from a parameterized complexity perspective and improve upon the 2k kernel of Lucas. Specifically, we describe a kernel of size 4k/3 and then show how it can be improved to (1 + ∈)k for every constant ∈>0. By ensuring that the kernel consists of a single instance our result yields a kernel of the same magnitude (up to additive terms) for the almost equivalent rotation distance problem on rooted, ordered binary trees. The earlier work of Lucas left the kernel as a disjoint set of instances, potentially allowing very minor differences in the definition of the size of instances to accumulate, causing a constant-factor distortion in the kernel size when switching between flip distance and rotation distance formulations. Our approach avoids this sensitivity. We have also undertaken experiments to understand how much reduction is achieved by our kernel in practice.
Collections
Language
  • English
Classification
Computer science and technology
License
CC BY
Open access status
hybrid
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1326702
Statistics
Document views: 18 File downloads:
  • Bosch-Calvo_2023_Else_ipl.pdf: 33