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.

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)