Geodesic Ham-Sandwich Cuts

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

doi:10.1007/s00454-006-1287-2

Geodesic Ham-Sandwich Cuts

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

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	325-339
Number of pages	15
Journal	Discrete and Computational Geometry
Volume	37
Issue number	3
DOIs	https://doi.org/10.1007/s00454-006-1287-2
State	Published - Mar 2007

ASJC Scopus subject areas

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

Access to Document

10.1007/s00454-006-1287-2

Cite this

@article{fd68be7a9f9c457c8529e98bc1df7c92,

title = "Geodesic Ham-Sandwich Cuts",

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.",

author = "Prosenjit Bose and Demaine, {Erik D.} and Ferran Hurtado and John Iacono and Stefan Langerman and Pat Morin",

year = "2007",

month = mar,

doi = "10.1007/s00454-006-1287-2",

language = "English (US)",

volume = "37",

pages = "325--339",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Geodesic Ham-Sandwich Cuts

AU - Bose, Prosenjit

AU - Demaine, Erik D.

AU - Hurtado, Ferran

AU - Iacono, John

AU - Langerman, Stefan

AU - Morin, Pat

PY - 2007/3

Y1 - 2007/3

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

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

UR - http://www.scopus.com/inward/record.url?scp=33947201057&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33947201057&partnerID=8YFLogxK

U2 - 10.1007/s00454-006-1287-2

DO - 10.1007/s00454-006-1287-2

M3 - Article

AN - SCOPUS:33947201057

SN - 0179-5376

VL - 37

SP - 325

EP - 339

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -

Geodesic Ham-Sandwich Cuts

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this