Algorithms, Combinatorics, and Optimization Seminar

  • Remote Access Enabled - Zoom
  • Virtual Presentation
  • Ph.D. Student
  • Department of Mathematical Sciences
  • Carnegie Mellon University

The necklace splitting problem and robot motion planning

In the necklace splitting problem, two thieves steal a necklace with k types of jewels and want to partition the necklace so that each thief gets half the jewels of each type, using the minimum number of cuts. At most k cuts are required; this result has a nice topological proof via the Borsuk–Ulam theorem, which involves representing the configuration space of possible cuts as a sphere. I will present several combinatorial results using similar techniques.

Recently, Lazarev and Lieb proved a smooth variant of the necklace splitting result. I will explain how the same technique, of representing the configuration space as a sphere and applying the Borsuk–Ulam theorem, can be used to generalize their result and improve the best-known quantitative bounds. Our approach also yields a result on motion planning algorithms; a motion planning algorithm is a continuous choice of paths for a robot to travel from any starting point to any ending point in a space.

Zoom Participation. See announcement.

For More Information, Please Contact: