Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem (Q2373932): Difference between revisions

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.