Computing a ham-sandwich cut in two dimensions

DOI10.1016/S0747-7171(86)80020-7zbMath0623.68058WikidataQ56428476 ScholiaQ56428476MaRDI QIDQ1091824

Herbert Edelsbrunner, Roman Waupotitsch

Publication date: 1986

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

computational geometryprune-and-searchgeometric transformsham- sandwich theorem

Mathematics Subject Classification ID

Searching and sorting (68P10) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

Bisecting envelopes of convex polygons ⋮ Algorithms for ham-sandwich cuts ⋮ Symbolic treatment of geometric degeneracies ⋮ Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\) ⋮ Ham-sandwich cuts for abstract order types ⋮ A geometric consistency theorem for a symbolic perturbation scheme ⋮ On the Complexity of the Pancake Problem ⋮ The catline for deep regression ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ A Complete Implementation for Computing General Dimensional Convex Hulls

Cites Work

• Edge-skeletons in arrangements with applications
• On the computational power of pushdown automata
• Partitioning with two lines in the plane
• Polygon Retrieval