**Reference**:- Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin, “Geodesic Ham-Sandwich Cuts”, in
*Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004)*, Brooklyn, New York, June 9–11, 2004, pages 1–9. **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 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*. **Comments**:- This paper is also available from the ACM Digital Library.
**Length**:- The paper is 9 pages.
**Availability**:- The paper is available in PostScript (809k), gzipped PostScript (280k), and PDF (275k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- GeodesicHamSandwich_DCG (Geodesic Ham-Sandwich Cuts)

See also other papers by Erik Demaine.

Last updated August 3, 2020 by Erik Demaine.