Computing a ham-sandwich cut in two dimensions
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.
- Dynamic ham-sandwich cuts in the plane
- Bisections and ham-sandwich cuts of convex polygons and polyhedra
- A linear algorithm for bisecting a polygon
- The catline for deep regression
- Algorithms for ham-sandwich cuts
- Green eggs and ham
- Computing balanced convex partitions of lines
- Bisecting envelopes of convex polygons
- Bisecting three classes of lines
- Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
- Symbolic treatment of geometric degeneracies
- Partitioning with two lines in the plane
- A Complete Implementation for Computing General Dimensional Convex Hulls
- OPTIMAL LINE BIPARTITIONS OF POINT SETS
- On the complexity of the pancake problem
- Geodesic ham-sandwich cuts
- Orthogonal ham-sandwich theorem in \(\mathbb{R}^3\)
- Weighted Ham-Sandwich Cuts
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- Computing balanced convex partitions of lines
- Optimal line bipartitions of point sets
- Geodesic ham-sandwich cuts
- Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)
- A geometric consistency theorem for a symbolic perturbation scheme
This page was built for publication: Computing a ham-sandwich cut in two dimensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1091824)
