===========================================================================
CSC 373H1 / L0101      Tutorial Notes -- Week  4            Winter 2012
===========================================================================

In two parts:

Part I. Go over the divide and conquer algorithm for computing mod(y^n, b) 
as provided by powerMod.pdf

========================================================================

Part II. Sketch Solution of  Problem: #5, p.248 of Kleinberg & Tardos

PROBLEM:  Hidden Lines.
 
Given parameters of n lines {(m_k, b_k)}_{k=1}^n, where the k-th
line L_k is given by
  y = m_k x + b_k
Find the "segments visible from above" (see hiddenLines.pdf,
sketch something similar on board).

In particular, define 
  F = {(x,y} | y >= m_k x + b_k for all k = 1, ... , n}

Then F is a convex polytope
  Defn: F convex iff for all a, b in F, and t in (0,1) we have 
  (1-t)a + tb is in F.

  Working-Defn: Polytope (in 2D) is a region whose boundary
  is specified by finitely many line segments.
 
PROBLEM: Given a set of lines {(m_k, b_k)}_{k=1}^n we want to find the 
boundary segments of the polytope F defined above.  
Can assume all the slopes (m_k's) are distinct.

===================
Attack #1
===================

Maybe we can iteratively add one line at a time.
How do we do that?

(See hiddenLinesFigures.pdf first page.)

Consider adding one line, say y = m_0 x + b_0 to 
a polytope we've already built.
Say polytope F bounded by lines k=1,...,n
Assume m_1 < ... < m_n.

Suppose we also keep information about the vertices
of the polytope F.  Namely the vertices are at
x = c_1, ... c_{n-1}.  Moreover, c_k is the x coordinate
of the intersection of line L_k and L_{k+1}. 
 
For simplicity here, assume the slope of the line
we are adding, m_0 is distinct from all the other slopes.
 
The question then is how do we update the set of line
parameters and the vertices for the new polytope 
F' = F intersect {(x,y) | y >= m_0 x + b_0}

================
Soln to one line update:

If m_0 < m_1, line L_0 must be "above" F for x sufficiently
negative.  Add L_0 to F.

If m_0 > m_n, line L_0 must be above F for x sufficiently large.
Add L_0 to F.

Otherwise:
  Eval u_k = (m_k c_k + d_k) - (m_0 c_k + b_0) 
         = y-value of kth vertex - y value of new line at c_k

  Let Neg = {k | u_k < 0}

  If Neg is empty. 
    F' = F.

  Otherwise, define s = min Neg and t = max Neg
  Update F 

VERY BRIEFLY SKETCH this in the picture (first plot in
hiddenLineFigures.pdf).  Ask them to fill in the details afterwards.

===========================
RUNTIME?

How many operations to add one line to a polytope consisting
of n boundary segments?  \Theta(n).

If we just iteratively add one line each time.  
  Sum_k=1...n T(add(1 line to k lines)) = \Theta(n^2)

===========================

Ok. What about trying Divide and Conquer?

Attack #2.  
Just split the set of lines (without any sorting) in half.

SUMMARIZE:  Hard to merge two general polytopes.

Sketch a situation where you are merging two general polytopes,
mix things up so bounding lines are used from both, and alternate
between the two polytopes ... 

Looks like we would need something like inserting each of the lines 
in polytope F2 into polytope F1.  In which case the merge
would be \Theta(n^2).

T(n) = 2T(n/2) + \Theta(n^2) => T(n) = \Theta(n^2)

haven't gained (asymptotically, at least)

==========================

Attack #3
JUST SKETCH THE IDEA HERE.
LEAVE THE REST FOR THEM TO THINK ABOUT
 
MAIN IDEA:
What about if we sort all the m_k's first? (O(n log n))

Then split the set of lines in half (smaller m_k's), (bigger m_k's).

DETAILS (can skip most of this, depending on the time):

Compute the polytopes P0 for smaller m_k's and P1 for bigger m_k's.
Time: 2T(n/2).

Sketch such a situation (see hiddenLineFigures.pdf, third page).

Suppose ck are the x-coords of the vertices in P0, and dk are the x-coords
for the vertices in P1.
 
Let ek be the sorted union of {c_k} U {d_k}.  (O(n) using merge).

Compute 
  u_k = dP1(ek) - dP0(ek) 
(where dP denotes the boundary of the polytope P... a piecewise 
linear function of x).  (How long to compute? O(n) with care to
keep track of which line segment to evaluate as you loop through the ek's)

Know dP1(x) - dP0(x) -> +infty as x - > infty 
because the slopes are biggest in P1.  And to -infty when x -> -infty.

Let s = min {k | u_k > 0}            (O(n))

Then dP1 and dP0 intersect once, between e_{s-1} and e_s.
Can find this intersection. O(1)
And update the line parameter list and the x-coordinate of the
vertex list in O(n).

Result:
  T(n) = 2T(n/2) + \Theta(n) therefore T(n) = \Theta(n log n).


===============