Geodesic ham-sandwich cuts

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

doi:10.1145/997817.997821

Geodesic ham-sandwich cuts

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

Research output: Contribution to conference › Paper › 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 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 language	English (US)
Pages	1-9
Number of pages	9
DOIs	https://doi.org/10.1145/997817.997821
State	Published - 2004
Event	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004

Other

Other	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Country/Territory	United States
City	Brooklyn, NY
Period	6/9/04 → 6/11/04

Keywords

Geodesics
Ham-sandwich
Shortest paths
Simple polygons

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/997817.997821

Cite this

@conference{2a937deffaec4abda1d026be3bc2191b,

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

keywords = "Geodesics, Ham-sandwich, Shortest paths, Simple polygons",

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

year = "2004",

doi = "10.1145/997817.997821",

language = "English (US)",

pages = "1--9",

note = "Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) ; Conference date: 09-06-2004 Through 11-06-2004",

}

TY - CONF

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 - 2004

Y1 - 2004

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

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

KW - Geodesics

KW - Ham-sandwich

KW - Shortest paths

KW - Simple polygons

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

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

U2 - 10.1145/997817.997821

DO - 10.1145/997817.997821

M3 - Paper

AN - SCOPUS:4544224052

SP - 1

EP - 9

T2 - Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)

Y2 - 9 June 2004 through 11 June 2004

ER -

Geodesic ham-sandwich cuts

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this