Algorithms for planning and interpolating movement

Abstract

Movement shapes the world around us, and studying it offers a way to better understand that world. Questions of movement are especially prominent today: vast quantities of movement data allow us to analyze past trajectories, while many practical tasks require us to plan future ones. Both endeavors must often contend with incomplete information, limited resources, and environmental constraints. In my thesis, “Algorithms for Planning and Interpolating Movement,” I study algorithmic problems in route planning and movement analysis across discrete and geometric environments. We develop efficient methods for computing, approximating, and analyzing paths and walks under structural, temporal, and geometric constraints. The results range from complexity and approximation algorithms for route optimization to practical tools for tour generation, stochastic trajectory reconstruction, and geometric shortestpath queries. The contributions span three complementary areas. First, we study variants of the Orienteering Problem, delineating tractability and hardness on paths, cycles, and trees and, for the Edge Orienteering Problem, providing a (4+ε)-approximation and investigating practical heuristics. Second, we develop methods for reconstructing movement from sparse trajectory data, using dynamic programming and conditioned random walks to compute transition densities, visit probabilities, utilization distributions, and individual trajectories. Finally, we study minimum-link paths in polygonal domains with holes, developing preprocessing and query structures for efficient two-point link-distance queries and polynomial-time computation of the link diameter, radius, and center. Together, these results combine structural complexity insights with efficient algorithms and practically applicable methods.