Ham-sandwich cuts for abstract order types
From MaRDI portal
Publication:1702128
DOI10.1007/s00453-016-0246-4zbMath1386.68193arXiv1503.02970OpenAlexW2909563536MaRDI QIDQ1702128
Stefan Felsner, Alexander Pilz
Publication date: 28 February 2018
Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1503.02970
Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Evaluating signs of determinants using single-precision arithmetic
- Semispaces of configurations, cell complexes of arrangements
- Construction of \(\epsilon\)-nets
- Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
- \(\epsilon\)-nets and simplex range queries
- Computing a ham-sandwich cut in two dimensions
- Topologically sweeping an arrangement
- Proof of a conjecture of Burr, Grünbaum, and Sloane
- On the combinatorial classification of nondegenerate configurations in the plane
- Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
- Axioms and hulls
- A combinatorial abstraction of linear programming
- Algorithms for ham-sandwich cuts
- Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
- Time bounds for selection
- Efficient algorithms for line and curve segment intersection using restricted predicates
- Ham-sandwich cuts for abstract order types
- Approximations and optimal geometric divide-and-conquer
- Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
- Extreme point and halving edge search in abstract order types
- Corrigendum: Topologically sweeping an arrangement
- Geodesic-Preserving Polygon Simplification
- Geodesic Order Types
- Multidimensional Sorting
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- Complexity of Some Geometric and Topological Problems
- Partitioning with two lines in the plane
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- Pseudo-Line Arrangements: Duality, Algorithms, and Applications
- Geodesic ham-sandwich cuts
- Automated Deduction in Geometry
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
