Computing a ham-sandwich cut in two dimensions (Q1091824)

According to the ham-sandwich theorem, for any two finite point sets in the plane there is a line that bisects both sets. Here we say that a line bisects a point set if at most half of the points lie in any open half- plane determined by the line. Lines that simultaneously bisect two point- sets have application to various geometric problems including range search in the plane. If the two (finite) point sets are separated (that is, their convex hulls are disjoint), then a line that bisects both sets can be found in O(n) time where n is the total number of points. A considerably more complicated algorithm involving e.g. a parallel sorting scheme can find such a line in O(n log n) time if the point sets are not separated. This paper extends the linear algorithm due to Megiddo to the case of non- separated sets and obtains an algorithm that runs in \(O((n_ 1+n_ 2) \log (\min \{n_ 1,n_ 2\}+1))\) time. The advantages of this algorithm over the O(n log n) scheme is that it is significantly simpler and that it is faster if \(n_ 1\) and \(n_ 2\), the cardinalities of the two sets, are very unbalanced. It is open whether or not linear time is sufficient to find a simultaneous bisector in the non-separate case.