An O(n) Algorithm of Hamsandwich Cut in R2

Basic Ideas

First, Let's recall the problem definition in the introduction. Given two point sets, Red and Blue, we want to find a line to biset both sets such that the number of red (blue) points are the same on each side of the line.

Here we introduce the algorithm from [LMS94]. In their algorithm, duality is used to map two point sets to two lines sets. For each line set, we have a median level of the line arrangement, which has half lines above and half lines below itself. Following this definition, it is not hard to see the intersection of these two median levels are the ham-sandwich cut in the prime plane. How do we find the intersections of the median-level? Here we use the so called "prune-and-search" technique again. In the algorithm, at each iteration, we discard a constant fraction of the existing lines which cannot have intersections in the median level. The iteration goes until we have constant number of lines and the ham-sandwich cut intersection can be searched directly. Each iteration takes time linear to the current number of lines and the number of lines decreases geometrically, the total running time is also linear.

Algorithm

Duality

Here we introduce the duality transform which maps the point p=(a,b) to line y=2ax-b. Let H denote the duality line sets. An important concept for us is the p-level in the arrangement of H, denoted by Lp(H). In the plane, this is the line segments of H , which has exactly p-1 lines below it. When p is half of the size of the line set, we call Lp(H) the median level of the arrangement of H. Now The dual version of the ham-sandwich cut problem can be restated as follows:

Given two line sets H1 and H2, find an intersection point of the median levels of the arrangements of H1 and H2.

Algorithm Outline

The algorithm runs in iteration. At the beginning of each iteration, it has the following data:

while we also maintain the following variants:

The f1 = Lp1(G1) and f2 = Lp2(G2) have an odd number of intersections within vertical strip V(T)={(x,y) | xT and yR} and each such intersection is an intersection of the median levels of the original line sets H1 and H2.

The algorithms runs like this (we suppose m1m2, otherwise renumber the sets)

  1. Divide the interval T into a constant number of subintervals Ti, where each vertical strip V(Ti) has most constant number of fraction of the vertices in the arrangement of Gi. [O(m1)]
  2. Find one subinterval Ti who has an odd number of such intersections. [O(m1 + m2)]
  3. Construct a trapezoid τ ⊂ V(Ti) such that the p1 level of the arrangement in the vertical strip is in the trapezoid τ and at most half of the lines of G1 intersect τ [O(m1)]
  4. Discard all the lines of G1 which do not intersect τ and update p1 accordingly, then Ti becomes the new T and we are ready for the next phase of the algorithm. [O(m1+m2)]

Detail Proof

Existence of Ham-Sandwich Cut Vertex

First let's prove the existence of ham-sandwich cut in R2. We use the duality to prove the existence. In the duality, we have the following

Lemma. The medial level of H1 and H2 must intersect in an odd number of points.

Proof. Here we give an geometric proof which also give some insight in the later phase of the algorithm. Consider the left unbounded ray and right unbounded ray of median level of H1, which belongs to the line of H1 having the median slope. It is same for the median level of H2. Call these two lines h1 and h2. Without loss of generality, let's assume l1 has a greater slope. So at a small enough x=l, we have h1(l) < h2(l) and at a large enough r, we have h1(r) = h2(x). Therefore, two median levels must have odd number of intersections because of the continuity.
Remark. Since the same reason of continuity, we can say an interval T=(l,r) has odd number of intersections with respect to λ1, the p1-levels of arrangement of H1, and λ2, p2-levels of arrangement of H2 if and only if odd condition

median level of two line sets

Median levels of two line sets intersect in an odd number of points.

Find Subinterval in Linear Time

Here we fill the detail of step 1 in the algorithm. That is we can find a constant number of intervals Ti and each vertical strip V(Ti) has at most αN vertices of the arrangement of G1, where α is a predetermined constant and N is the number of vertices of the arrangement of H.

To achieve this, we apply a theorem from [Mat90]. Let ti denote the x-coordinates of the vertices of H, in order. Given a positive constant v<1 and a number k, 1 ≤ kN, in linear time, we can find an intersection of two lines in H lies between tk-vN and tk+vN. Here we take v=α/4 and k=iαN / 2, run algorithm with i through 1 to 2/α, we can get an intersection with x-coordinate ui lies in two ti in linear time. Let the new interval Ti=(ui-1, ui). With a little calculation, we can prove the vertices in V(Ti) cannot be more than αN and the number of intervals is bounded by 2/α.

Decide the Odd Intersection Property of Interval Ti

When the step above finishes, we have a constant number of intervals. Now we want to find one of them that has odd number of intersections of p1-level arrangement of H1 and p2-level arrangement of H2 in the interval Ti=(l,r).

If T is bounded, we calculate all the y-coordinate of lines in H1 at x=l and use a linear selection algorithm to pick the p1th value. We do the same thing for H1 at x=r and H2 at x=l,r with picking p2th value. If some side of T is unbounded, we use linear selection algorithm to find the line with corresponding slope. Finally, we use the formular to test the odd intersection property.

Construct the Trapezoid and Its Properties

After we locate the search interval, it is time for us to decide what kind of lines to discard. To achieve this, we construct a trapezoid to verify some properties of the line. More specifically, given an interval T=(l,r), we find the intersections of x=l and p1 - εm level, p1 + εm level of the arrangement of H1, denoting by D-l, D+l. Through the same approach, we have D-r, D+r. These four points are the four vertices of the trapezoid τ.

trapezoid of red lines

Trapezoid τ of red lines with median level as p1.

Consider the top of τ, the segment δ=D+lD+r. The lines in G1 that meet δ can be partitioned into two classes, P, the lines with slope greater the slope of δ and those with slope smaller than the slope of δ. Traversing δ from left to right, we count the number of lines below δ. When we meet a line in P, the counter decreases by one; while a line in Q increases the counter by one. Since the start and end have the same number of lines below δ (they are both in level p1 + εm), |P|=|Q|.

Each line in P will intersect each line in Q within the vertical strip V(Ti). Since the number of vertices in the strip is at most we have Since δ is εm1 lines above p1 level at both endpoints of the interval Ti. To ensure p1-level remains below δ, we should have εm1 - |P|≥ 0, that is The vertical side D+lD-l and D+rD-r of trapezoid τ have most 2εm1 intersections on each side by definition. Thus the total intersections is less than 8εm1. Each line in G1 meets τ intersects two sides, at most 4εm1 lines can meet the trapezoid. Let ε = 1/8, at least half the lines in G1 miss τ. We now take α=1/32 so the constraints between α and ε are met.