Paper by Erik D. Demaine

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

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.

Comments:
This paper is also available from SpringerLink.

Length:
The paper is 13 pages.

Availability:
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 March 12, 2024 by Erik Demaine.