Animation scientifique

Reconfiguration problems ask whether one feasible geometric structure can be transformed into another through small local changes while remaining valid throughout. Typically, it is an easy exercise to prove connectivity of a flip graph. In contrast, the connectivity of the flip graph of plane spanning paths on point sets in general position has been an open problem for 19 years.

In this talk, I focus on two structured families of plane spanning paths: stars and generalized spirals. A star visits all points in angular order around a chosen center, while a generalized spiral winds around a center with a consistent orientation. For both families, we prove polynomial bounds on the number of flips needed to transform one path into another: two stars with the same fixed start can be reconfigured using O(n^3) flips, and only O(n) when endpoints are free. The same pattern holds for generalized spirals, with cubic bounds for fixed starts and linear bounds proportional to the number of revolutions when endpoints vary.

These results yield a polynomial‑time reconfiguration method for suffix‑independent paths, improving previous exponential bounds. We also complement our theoretical results with experiments on efficiently transforming arbitrary paths into stars in practice.