Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
An interesting consequence of the famous Borsuk-Ulam theorem is the so-called ham-sandwich theorem, which says that given \(m\) finite continuous measures on \(R^m\), there exists a hyperplane that simultaneously bisects them. This paper deals with its discrete versions and the computational complexities of the algorithms in finding the ``hyperplanes, which are said to be ham-sandwich cuts. Given \(n\) points in general position in \(R^2\), \textit{D. Willard} asked in [SIAM J. Comput. 11, 149--165 (1982; Zbl 0478.68060)] if there is a pair of non-parallel lines \(l_1\) and \(l_2\) that equitably partition the \(n\) points, i.e. each of the four open complements of \(l_1\cup l_2\) contains at most \(n/4\) points. This was solved by \textit{R. Cole, M. Sharir} and \textit{C. Yap} [SIAM J. Comput. 16, 61--77 (1987; Zbl 0637.68074)]. The authors show that the two lines can be orthogonal and may be found in \(O(n\log n)\) RAM steps by describing some algorithms. Meanwhile, these algorithms provide a direct proof of the existence of the ham-sandwich cuts. The authors also present \(O(n\log n)\) algorithms finding another kind of ham-sandwich cuts for \(n\) points in general position in \(R^2\). Such as: three lines having a common point such that each of the six open complements of the union of the three lines contains at most \(n/6\) points, a convex quadrilateral and two lines through its opposite vertices such that each of the eight open regions determined by the quadrilateral and the two lines has at most \(n/8\) points.
- Dynamic ham-sandwich cuts in the plane
- Algorithms for ham-sandwich cuts
- Orthogonal ham-sandwich theorem in \(\mathbb{R}^3\)
- Generalizing ham sandwich cuts to equitable subdivisions
- Weighted Ham-Sandwich Cuts
- Computing balanced convex partitions of lines
- Computing a ham-sandwich cut in two dimensions
- Computing balanced convex partitions of lines
- Equitable subdivisions within polygonal regions
- Generalized ham-sandwich cuts
- Algorithms for ham-sandwich cuts
- An equipartition of planar sets
- An improved bound for \(k\)-sets in three dimensions
- An Optimal-Time Algorithm for Slope Selection
- Balanced convex partitions of measures in \(\mathbb R^{2}\)
- Balanced partitions of two sets of points in the plane
- Bisection of Circle Colorings
- Equipartition of two measures by a 4-fan
- Equipartitions of measures by 2-fans
- Generalizing ham sandwich cuts to equitable subdivisions
- Geodesic ham-sandwich cuts
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 1962801 (Why is no real title available?)
- scientific article; zbMATH DE number 1507295 (Why is no real title available?)
- Improved bounds for planar k-sets and related problems
- On k-Hulls and Related Problems
- Partitioning Space for Range Queries
- Partitioning with two lines in the plane
- Polygon Retrieval
- Simultaneous partitions of measures by \(k\)-fans
- Splitting necklaces
- The Borsuk-Ulam Theorem and Bisection of Necklaces
- Weighted Ham-Sandwich Cuts
- Points with large \(\alpha \)-depth
- Computing a ham-sandwich cut in two dimensions
- Generalizing ham sandwich cuts to equitable subdivisions
- Fault-tolerant spanners in networks with symmetric directional antennas
- Computing balanced islands in two colored point sets in the plane
- Computing balanced convex partitions of lines
- Bisecting envelopes of convex polygons
- Ham-sandwich cuts and center transversals in subspaces
- Algorithms for finding connected separators between antipodal points
- The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics
- scientific article; zbMATH DE number 431992 (Why is no real title available?)
- Computing generalized ham-sandwich cuts
- Ham Sandwich is equivalent to Borsuk-Ulam
- A survey of mass partitions
- The Borsuk-Ulam theorem and combinatorics
- Orthogonal ham-sandwich theorem in \(\mathbb{R}^3\)
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- Generalized ham-sandwich cuts
- An application of Borsuk-Ulam's theorem to parametric optimization
- Computing balanced convex partitions of lines
- On the enumeration of subcells within hypercubes and its application to the Borsuk-Ulam theorem
- Bisections of mass assignments using flags of affine spaces
- Acute tours in the plane
- An FPT algorithm for splitting a necklace among two thieves
- An FPT algorithm for splitting a necklace among two thieves
- On the orthogonal Grünbaum partition problem in dimension three
- Unfairly splitting separable necklaces
This page was built for publication: Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373932)
