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.

BibTeX

@Article{GeodesicHamSandwich_DCG,
  AUTHOR        = {Prosenjit Bose and Erik D. Demaine and Ferran Hurtado and
                   John Iacono and Stefan Langerman and Pat Morin},
  TITLE         = {Geodesic Ham-Sandwich Cuts},
  JOURNAL       = {Discrete \& Computational Geometry},
  journalurl    = {http://link.springer.de/link/service/journals/00454/},
  VOLUME        = 37,
  NUMBER        = 3,
  MONTH         = {March},
  YEAR          = 2007,
  PAGES         = {325--339},

  length        = {13 pages},
  replaces      = {GeodesicHamSandwich_SoCG2004},
  papers        = {GeodesicHamSandwich_SoCG2004},
  doi           = {https://dx.doi.org/10.1007/s00454-006-1287-2},
  dblp          = {https://dblp.org/rec/journals/dcg/BoseDHILM07},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/s00454-006-1287-2">SpringerLink</A>.},
}

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)