An improved kernel for the flip distance problem on simple convex polygons
Informazioni aggiuntive
Autori
Bosch-Calvo M.,
Kelk S.
Tipo
Articolo pubblicato in rivista scientifica
Anno
2023
Lingua
Inglese
Sommario
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.
Parole chiave
Algorithms, Parameterized complexity, Kernel, Triangulation, Simple convex polygons
Periodico
Information processing letters
Volume
182
Pagine (o numero dell’articolo)
106381
Diffusione
Licenza
CC BY
Visibilità
Pubblico
Status open access
Hybrid
