Dynamic ham-sandwich cuts in the plane
type: Item
instance of: scholarly article
title: Dynamic ham-sandwich cuts in the plane
zbMATH Open document ID: 1181.65029
author: Timothy G. Abbott
author: Michael A. Burr
author: Timothy M. Chan
author: Erik D. Demaine
author: Martin L. Demaine
author: John Hugg
author: Stefan Langerman
author: Jelani Nelson
author: Eynat Rafalin
author: Kathryn Seyboth
author: Vincent Yeung
author: Daniel M. Kane
published in: Computational Geometry
publication date: 2009-06-18T00:00:00Z
full work available at URL: http://hdl.handle.net/1721.1/96191
review text: The two-dimensional version of the ham-sandwich theorem states that any two compact sets in the plane can be simultaneously bisected by a single line. Algorithms for determining such a bisecting line have been studied extensively; however, almost all such algorithms do not consider the possibility of dynamically altering the planar sets. In this paper, the authors present data structures and algorithms that allow for efficient bisector determination as well as dynamic insertion and deletion of points. The authors discuss the cases when each of the two sets is specified as a collection of points, or as a union of convex polygons; in the latter case, either the vertex count, perimeter, or area may be used as the measure by which to bisect. Also discussed is the related problem of partitioning a set into four equal parts using only two lines. Although the authors address an audience versed only in the generalities of computational geometry, the discussion makes extensive use of previous results. The overall exposition is terse, although abundant references are provided.
reviewed by: Jason Hanson
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 52B55
zbMATH DE Number: 5566424
zbMATH Keywords: data structures
zbMATH Keywords: bisectors
zbMATH Keywords: point sets
zbMATH Keywords: polygons
zbMATH Keywords: ham-sandwich theorem
zbMATH Keywords: algorithms
zbMATH Keywords: computational geometry
MaRDI profile type: Publication
OpenAlex ID: W2102891664
cites work: Ray Shooting and Parametric Search
cites work: Dynamic half-space range reporting and its applications
cites work: Geodesic ham-sandwich cuts
cites work: Weighted Ham-Sandwich Cuts
cites work: The Early History of the Ham Sandwich Theorem
cites work: Introduction to algorithms
cites work: Slowing down sorting networks to obtain faster sorting algorithms
cites work: On k-Hulls and Related Problems
cites work: Counting the onion
cites work: Q3956222
cites work: Q3772828
cites work: The complexity of selection and ranking in X+Y and matrices with sorted columns
cites work: Q4547801
cites work: On the complexity of halfspace area queries
cites work: Algorithms for ham-sandwich cuts
cites work: Efficient partition trees
cites work: Reporting points in halfspaces
cites work: Applying Parallel Computation Algorithms in the Design of Serial Algorithms
cites work: Partitioning with two lines in the plane
cites work: Computational Geometry in C
cites work: Solving a Polynomial Equation: Some History and Recent Progress
cites work: Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
cites work: Generalized ''sandwich'' theorems
cites work: Bisections and ham-sandwich cuts of convex polygons and polyhedra
DOI: 10.1016/J.COMGEO.2008.09.008
description: scientific article; zbMATH DE number 5566424