An improved kernel for the flip distance problem on simple convex polygons
Additional information
Authors
Bosch-Calvo M.,
Kelk S.
Type
Journal Article
Year
2023
Language
English
Abstract
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.
Keywords
Algorithms, Parameterized complexity, Kernel, Triangulation, Simple convex polygons
Journal
Information processing letters
Volume
182
Pages (or article number)
106381
Diffusion
License
CC BY
Visibility
Public
Status open access
Hybrid
