Geodesic ham-sandwich cuts

Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin

    Research output: Contribution to conferencePaperpeer-review


    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 languageEnglish (US)
    Number of pages9
    StatePublished - 2004
    EventProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States
    Duration: Jun 9 2004Jun 11 2004


    OtherProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
    Country/TerritoryUnited States
    CityBrooklyn, NY


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

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics


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

    Cite this