Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Bose, P., Demaine, E., Hurtado, F. et al. Geodesic Ham-Sandwich Cuts. Discrete Comput Geom 37, 325–339 (2007). https://doi.org/10.1007/s00454-006-1287-2
Issue Date:
DOI: https://doi.org/10.1007/s00454-006-1287-2