Geodesic Ham-Sandwich Cuts

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

    Research output: Contribution to journalArticle

    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

    Bose, P., Demaine, E. D., Hurtado, F., Iacono, J., Langerman, S., & Morin, P. (2007). Geodesic Ham-Sandwich Cuts. Discrete and Computational Geometry, 37(3), 325-339. https://doi.org/10.1007/s00454-006-1287-2