|
Step To Find the Ham Sandwich Cut
|
Step 1.
- Two point sets are created, P and Q
|
Step 2.
- For each point in set P and Q we take the Dual
and create line sets H1 and H2 respectively.
|
Step 3.
- We divide the entire x-axis into C intervals so that each interval contains no more than a*N
intersections between the lines.
- Where C is the total number of intervals
- a < 1, and is chosen before we begin the
algorithm,
- And N is the total number of intersection
between all the lines
- This gives us C intervals with less than a*N intersections
each.
The picture below shows a set of lines that have
been divided up into intervals by the green lines.
Above the blue lines are the dual of the blue points and
the red lines are the dual of the red points
|
Step 4.
- We check all the intervals until we find one that
has the odd
intersection property.
- We will call this interval "Io"
("I" for Intersection and "o" for odd!)
In the picture above, (which is a zoomed in view of an
interval) the black dots represent the median level of the blue lines
and the pink dots represent the median levels of the red lines.
Since the median levels are flipped, this means that this interval has
the odd intersection property. The green dots are the
intersections of all the lines, if you count them there are 19!
|
Step 5.
- Now we construct a trapezoid inside our interval
"Io".
- For this step we are only concerned with one of the
sets of lines (the larger of the two sets). In the picture
below we choose the blue lines.
- We look at all the blue lines that intersect the
trapezoid and all the blue lines that do not intersect it. We
throw away all the lines that do not intersect it, since these are
not the median level.
Above in the picture, our trapezoid is denoted by the
orange lines. Looking at it we can see that each of the
corners of the trapezoid are exactly one line above or one line
below the median level of the blue points.
|
|
Creating the Trapezoid
- To create the vertices of the trapezoid we find the
number M, that will be the number of levels above or below the
median level.
- To find this number we subtract a fraction of the
total number of blue lines from the current median level P.
- In there there algorithm they use the 1/8 of the
total number of blue lines.
|
|
Finishing the Algorithm
-
Once we are finished creating the
trapezoid, we throw away at least 1/2 of the blue lines.
-
We continue repeating steps 3-5 until
we have removed enough blue lines so that it is easy to find a ham
sandwich cut in linear time.
|
