**Reference**:- Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin, “Geodesic Ham-Sandwich Cuts”,
*Discrete & Computational Geometry*, volume 37, number 3, March 2007, pages 325–339. **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*. **Comments**:- This paper is also available from SpringerLink.
**Length**:- The paper is 13 pages.
**Availability**:- The paper is available in PostScript (532k), gzipped PostScript (178k), and PDF (197k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- GeodesicHamSandwich_SoCG2004 (Geodesic Ham-Sandwich Cuts)

See also other papers by Erik Demaine.

Last updated March 12, 2024 by Erik Demaine.