Paper by Erik D. Demaine

Reference:

Timothy Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, and Vincent Yeung, “Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane”, in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), Windsor, Ontario, Canada, August 10–12, 2005, pages 61–64.

BibTeX

@InProceedings{DynamicHamSandwich_CCCG2005,
  AUTHOR        = {Timothy Abbott and Erik D. Demaine and Martin L. Demaine and
                   Daniel Kane and Stefan Langerman and Jelani Nelson and
                   Vincent Yeung},
  TITLE         = {Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane},
  BOOKTITLE     = {Proceedings of the 17th Canadian Conference on Computational
                   Geometry (CCCG 2005)},
  bookurl       = {http://cccg.cs.uwindsor.ca/},
  ADDRESS       = {Windsor, Ontario, Canada},
  MONTH         = {August 10--12},
  YEAR          = 2005,
  PAGES         = {61--64},

  award         = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.},
  length        = {4 pages},
  withstudent   = 1,
  unrefereed    = 1,
  ee            = {http://www.cccg.ca/proceedings/2005/79.pdf},
  papers        = {DynamicHamSandwich_CGTA},
  dblp          = {https://dblp.org/rec/conf/cccg/AbbottDDKLNY05},
}

Abstract:

We provide an efficient data structure for dynamically maintaining a ham-sandwich cut of two non-overlapping convex polygons in the plane. Given two non-overlapping convex polygons P₁ and P₂ in the plane, the ham-sandwich cut of P₁ and P₂ is a line that simultaneously bisects the area (or perimeter or vertex count) of both polygons. We provide a data structure that supports queries for the ham-sandwich cut in O(log³ n) worst-case time and insertions and deletions of vertices of the P_i in O(log n) worst-case time. We also show how this data structure can be used to maintain a partition of the plane by two lines into four regions each containing a quarter of the total polygon area (or perimeter or vertex count). In particular, if we use the vertex-count measure, the intersection of these two lines gives a point of Tukey depth n/4, which serves as an approximate Tukey median.

Length:

The paper is 4 pages.

Availability:

The paper is available in PostScript (256k), gzipped PostScript (115k), and PDF (142k).

See information on file formats.

[Google Scholar search]

Related papers:

DynamicHamSandwich_CGTA (Dynamic Ham-Sandwich Cuts in the Plane)