How to get from A to B?
How to get from A to B?
János Pach
Rényi Institute of Mathematics, Budapest
ABSTRACT
Starting with the famous "14-15 puzzle" attributed to Sam Loyd, many geometric, combinatorial, algebraic, and algorithmic questions can be phrased in the following form. Given two configurations, A and B, how can one transform A to B through a sequence of moves of a given type? Is this possible at all? We discuss several problems of this kind, including a basic problem in motion planning (joint work with Herbert Edelsbrunner), and a more recent puzzle by Kovaldzhi and Brunck with linear algebraic background (joint work with Gábor Tardos). We will also state some challenging open problems.