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

Original language | English (US) |
---|---|

Pages | 1-9 |

Number of pages | 9 |

DOIs | |

State | Published - 2004 |

Event | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004 |

### Other

Other | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) |
---|---|

Country | United States |

City | Brooklyn, NY |

Period | 6/9/04 → 6/11/04 |

### Keywords

- Geodesics
- Ham-sandwich
- Shortest paths
- Simple polygons

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Geodesic ham-sandwich cuts'. Together they form a unique fingerprint.

## Cite this

Bose, P., Demaine, E. D., Hurtado, F., Iacono, J., Langerman, S., & Morin, P. (2004).

*Geodesic ham-sandwich cuts*. 1-9. Paper presented at Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04), Brooklyn, NY, United States. https://doi.org/10.1145/997817.997821