# An *O*(*n*) Algorithm of Hamsandwich Cut in R^{2}

## 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*=2*ax*-*b*. Let *H* denote the duality line sets. An important concept for us is
the *p-level* in the arrangement of *H*, denoted by *L*_{p}(*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 *L*_{p}(*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 setsH_{1}andH_{2}, find an intersection point of the median levels of the arrangements ofH_{1}andH_{2}.

### Algorithm Outline

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

- an open interval
*T*on the*x*-axis, - current line sets
*G*_{1}and*G*_{2},*G*_{i}⊆*H*_{i}, |*G*_{i}|=*m*_{i}, - integers
*p*_{1},*p*_{2}, 1 ≤*p*_{i}≤*m*_{i}

while we also maintain the following variants:

Thef_{1}=L_{p1}(G_{1}) andf_{2}=L_{p2}(G_{2}) have an odd number of intersections within vertical stripV(T)={(x,y) |x∈Tandy∈R} and each such intersection is an intersection of the median levels of the original line setsH_{1}andH_{2}.

The algorithms runs like this (we suppose *m*_{1} ≥ *m*_{2}, otherwise
renumber the sets)

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

### Detail Proof

#### Existence of Ham-Sandwich Cut Vertex

First let's prove the existence of ham-sandwich cut in *R*^{2}. We use the duality
to prove the existence. In the duality, we have the following

Lemma.The medial level ofH_{1}andH_{2}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 ofH_{1}, which belongs to the line ofH_{1}having the median slope. It is same for the median level ofH_{2}. Call these two linesh_{1}andh_{2}. Without loss of generality, let's assumel_{1}has a greater slope. So at a small enoughx=l, we haveh_{1}(l) <h_{2}(l) and at a large enoughr, we haveh_{1}(r) =h_{2}(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 intervalT=(l,r) has odd number of intersections with respect to λ_{1}, thep_{1}-levels of arrangement ofH_{1}, and λ_{2},p_{2}-levels of arrangement ofH_{2}if and only if

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 *T*_{i} and each vertical strip *V*(*T*_{i})
has at most α*N* vertices of the arrangement of *G*_{1}, 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 *t*_{i} denote the
*x*-coordinates of the vertices of *H*, in order. Given a positive constant
*v*<1 and a number *k*, 1 ≤ *k* ≤ *N*, in linear time, we can find an
intersection of two lines in *H* lies between *t*_{k-vN} and *t*_{k+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 *u*_{i} lies in two
*t*_{i} in linear time. Let the new interval *T*_{i}=(*u*_{i-1}, *u*_{i}). With a little
calculation, we can prove the vertices in *V*(*T*_{i}) cannot be more than
α*N* and the number of intervals is bounded by 2/α.

#### Decide the Odd Intersection Property of Interval *T*_{i}

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 *p*_{1}-level
arrangement of *H*_{1} and *p*_{2}-level arrangement of *H*_{2} in the interval
*T*_{i}=(*l*,*r*).

If *T* is bounded, we calculate all the *y*-coordinate of lines in *H*_{1} at
*x*=*l* and use a linear selection algorithm to pick the *p*_{1}th value. We do the
same thing for *H*_{1} at *x*=*r* and *H*_{2} at *x*=*l*,*r* with picking *p*_{2}th
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 *p*_{1} - ε*m* level, *p*_{1} + ε*m*
level of the arrangement of *H*_{1}, 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 with median level as *p*_{1}.

Consider the top of τ, the segment δ=*D*^{+}_{l}*D*^{+}_{r}. The lines in
*G*_{1} 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 *p*_{1} +
ε*m*), |*P*|=|*Q*|.

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