Geodesic Ham-Sandwich Cuts

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

    Research output: Contribution to journalArticlepeer-review

    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.

    Original languageEnglish (US)
    Pages (from-to)325-339
    Number of pages15
    JournalDiscrete and Computational Geometry
    Volume37
    Issue number3
    DOIs
    StatePublished - Mar 2007

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics

    Fingerprint Dive into the research topics of 'Geodesic Ham-Sandwich Cuts'. Together they form a unique fingerprint.

    Cite this