Geodesic ham-sandwich cuts
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.
|Keywords||Geodesics, Ham-sandwich, Shortest paths, Simple polygons|
|Conference||Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)|
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).