Paper by Erik D. Demaine

Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin, “Geodesic Ham-Sandwich Cuts”, Discrete & Computational Geometry, volume 37, number 3, March 2007, pages 325–339.

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.

This paper is also available from SpringerLink.

The paper is 13 pages.

The paper is available in PostScript (532k), gzipped PostScript (178k), and PDF (197k).
See information on file formats.
[Google Scholar search]

Related papers:
GeodesicHamSandwich_SoCG2004 (Geodesic Ham-Sandwich Cuts)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 17, 2017 by Erik Demaine.