Algorithms for ham-sandwich cuts
From MaRDI portal
Publication:1329191
DOI10.1007/BF02574017zbMath0806.68061WikidataQ56428477 ScholiaQ56428477MaRDI QIDQ1329191
Chi-Yuan Lo, William Steiger, Ji{ří} Matoušek
Publication date: 29 June 1994
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131310
Related Items
On the expected number of \(k\)-sets, Bisecting envelopes of convex polygons, Geometric systems of unbiased representatives, An optimal algorithm for plane matchings in multipartite geometric graphs, New variants of perfect non-crossing matchings, A semi-algebraic version of Zarankiewicz's problem, An Optimal Algorithm for Plane Matchings in Multipartite Geometric Graphs, Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem, A survey of mass partitions, Extreme point and halving edge search in abstract order types, Equipartition of mass distributions by hyperplanes, Discrete geometry on colored point sets in the plane -- a survey, Packing 1-plane Hamiltonian cycles in complete geometric graphs, Generalized ham-sandwich cuts, Illumination by floodlights, Reprint of: Extreme point and halving edge search in abstract order types, Linear transformation distance for bichromatic matchings, Ham-sandwich cuts for abstract order types, Unnamed Item, Unnamed Item, On geometric graphs on point sets in the plane, Few cuts meet many point sets, A stronger conclusion to the classical ham sandwich theorem, Cubic plane graphs on a given point set, Algorithms for bivariate zonoid depth, Bisecting three classes of lines, New variants of perfect non-crossing matchings, Separating collections of points in Euclidean spaces, An optimal randomized algorithm for \(d\)-variate zonoid depth, On the Complexity of the Pancake Problem, New challenges in dynamic load balancing, Equitable subdivisions within polygonal regions, Bisecting a 4-connected graph with three resource sets, Dynamic ham-sandwich cuts in the plane, Small weak epsilon-nets, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, A robust algorithm for bisecting a triconnected graph with two resource sets, The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
Cites Work
- Unnamed Item
- Unnamed Item
- Construction of \(\epsilon\)-nets
- Sorting in \(c \log n\) parallel steps
- A matching problem in the plane
- Computing a ham-sandwich cut in two dimensions
- Edge-skeletons in arrangements with applications
- Points and triangles in the plane and halving planes in space
- Randomized optimal algorithm for slope selection
- An upper bound on the number of planar \(K\)-sets
- The colored Tverberg's problem and complexes of injective functions
- On the expected number of \(k\)-sets
- Partitioning with two lines in the plane
- On k-Hulls and Related Problems
- An Optimal-Time Algorithm for Slope Selection
- Polygon Retrieval
- Point Selections and Weak ε-Nets for Convex Hulls
- Constructing Belts in Two-Dimensional Arrangements with Applications
- A RANDOMIZED ALGORITHM FOR SLOPE SELECTION
