Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m + r + b. A ham-sandwich geodesic is a shortest path in P between two points on the boundary of P that simultaneously bisects the red points and the blue points. We present an O(n log k)-time algorithm for finding a ham-sandwich geodesic. We also show that this algorithm is optimal in the algebraic computation tree model when parameterizing the running time with respect to n and k.

Discrete and Computational Geometry
School of Computer Science

Bose, P, Demaine, E.D. (Erik D.), Hurtado, F. (Ferran), Iacono, J. (John), Langerman, S. (Stefan), & Morin, P. (2007). Geodesic Ham-Sandwich Cuts. Discrete and Computational Geometry, 37(3), 325–339. doi:10.1007/s00454-006-1287-2