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
Published in:
- Information processing letters. - 2023, vol. 182, p. 106381
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
-
-
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