Paper by Erik D. Demaine
- Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin, “Geodesic Ham-Sandwich Cuts”, in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 1–9.
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
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.
- This paper is also available from the ACM Digital Library.
- The paper is 9 pages.
- The paper is available in PostScript (809k), gzipped PostScript (280k), and PDF (275k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- GeodesicHamSandwich_DCG (Geodesic Ham-Sandwich Cuts)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 21, 2021 by