Giovanna Kobus Conrado
Advisor: Cristina G. Fernandes
Given two disjoint sets P1 and P2 in ℝ2, a two-dimensional ham sandwich cut is a line that bisects both P1 and P2 simultaneously. The ham sandwich problem consists of finding such a line. A linear-time algorithm to solve this problem was proposed by Chi-Yuan Lo, Jirí Matousek and William Steiger. We expand on their paper, detailing the steps needed to implement the algorithm, presenting pseudocode for most of the steps, and providing some of the knowledge needed to understand both the algorithm and why it works.