Geodesic ham-sandwich cuts

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

    Research output: Contribution to conferencePaper

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

    Other

    OtherProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
    CountryUnited States
    CityBrooklyn, NY
    Period6/9/046/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