Algorithms for Clustering, Partitioning, and Planning

We explore three geometric optimization problems with multifaceted goals, including efficiency, fairness, solution quality, and interpretability. The problems we study pose significant challenges because they involve complex geometric objects that interact in high-dimensional spaces. To contend with these challenges, our work utilizes realistic input structure to design algorithms that provide provably good solutions. Alternatively, we can approach the general problem statement with heuristic or approximate schemes.

The first problem domain addressed is trajectory clustering, where the goal is to partition noisy trajectories (polygonal curves) into clusters based on shared structure and find a representative trajectory for each cluster. We present a near-linear time (1+\eps)-approximation algorithm for k-median clustering of polygonal trajectories under the discrete Fréchet distance and finite point sets under the Hausdorff distance. The algorithm leverages the geometric properties of the trajectories, specifically that centers come from a "simpler" metric space, to achieve efficient clustering results.

The second problem we consider is redistricting, aiming to partition a given population into geographic regions in a fair and representative way. Redistricting involves drawing boundaries for electoral districts, which can significantly impact political representation and decision-making processes. We introduce a new model of fairness for the problem of fair redistricting and investigate the existence and computability of fair partitions. We consider this problem in both one and two dimensions. We also propose a new method of generating redistricting plans that leads to more compact (geometrically "nice") districts.

The final problem addressed is optimal motion planning for multiple robots in polygonal environments with obstacles. Each robot is represented a simple polygonal object, such as a unit disc or square. We present algorithms for generating motion plans which approximately minimize the sum of distances traveled from a start to target configuration. For the simplified case of two robots and given the paths the robots must traverse, we also give an algorithm to minimize the makespan (latest arrival time) of our schedule.