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 any 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.

Additional Metadata
Keywords Geodesics, Ham-sandwich, Shortest paths, Simple polygons
Conference Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Citation
Bose, P, Demaine, E.D. (Erik D.), Hurtado, F. (Ferran), Iacono, J. (John), Langerman, S. (Stefan), & Morin, P. (2004). Geodesic ham-sandwich cuts. Presented at the Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04).