\documentclass{article}
\input{6856-preamble}
\usepackage{clrscode}

\begin{document}
\psetnum{8}
\date{2005/04/06}
\collab{Collaborators: $\set{\mathtt{sarahl}, \mathtt{gpickard}}$}

\begin{pset}
  \begin{problem}
    Let $S$ be a set of vectors in a $d$-dimensional space, sampled
    independently with probability $p$. We show that the expected
    number of vectors not spanned by the sample (call this $V$) is no
    greater than $\nicefrac dp$.

    Let $\vec{x_1}, \ldots, \vec{x_b}$ ($b \le d$) be an
    orthonormal basis for the vectors in $S$. Denote by $n_i$ the
    number of vectors in $S$ that have a component in the $\vec{x_i}$
    direction, and let $X_i$ be the indicator random variable
    corresponding to the event that no vector having a component in
    the $\vec{x_i}$ direction is sampled. Then the expected number of
    vectors not spanned is
    \[ \Exp{V} = \sum_{i = 1}^b n_i \Exp{X_i} \]

    Consider the probability that $X_i = 1$, i.e. that no vector
    having a $\vec{x_i}$ component is sampled. There are $n_i$ such
    vectors, and each is sampled with probability $p$, so the
    probability of this event is $(1 - p)^{n_i}$. Thus,
    \[ \Exp{V} = \sum_{i = 1}^b n_i  (1-p)^{n_i} \]

    \begin{lemma}
      For $0 \le p \le 1$ and $n_i > 0$, $n_i(1-p)^{n_i} \le
      \frac{1}{p}$.
    \end{lemma}
    \begin{proof}
      We find the maximum of this function in the standard way, by
      taking the derivative with respect to $n_i$ and setting it equal
      to zero. This tells us that the maximum is at $n_i =
      \frac{-1}{\ln (1 - p)}$, where the function takes value
      $\frac{-1}{\ln (1 - p)} \frac{1}{e}$.
      
      Recall the inequality $e^t \ge 1 + t$. Under the (monotonic)
      logarithmic transformation, $t \ge \ln 1 + t$. Taking $t = -p$,
      \[ - \ln (1 - t) \ge p \]
      and so
      \[ \frac{-1}{\ln (1 - p)} \le \frac{1}{p} \]
      which proves the lemma.
    \end{proof}

    Applying the lemma, we find that
    \[ \Exp{V} \le \sum_{i = 1}^b \frac{1}{p} \le \frac{b}{p} \le
    \frac{d}{p} \]
    which proves the claim.
  \end{problem}

  \begin{problem}
    Recall the result of the painstaking analysis in class for the
    non-iterative-reweighting algorithm:  if we have a set $S$ of $m$
    constraints, and we sample a set $R$ of $r$ constraints uniformly
    at random, then the expected number of constraints in $S$ that
    violate the optimum of $R$ is $\frac{d (m - r + 1)}{r - d}$.
    
    Now we are given $n$ constraints, each of which has a positive
    integer weight $w_h$. We replace each constraint $h$ with $w_h$
    ``virtual copies'' of itself. Then we consider sampling uniformly
    from the resulting set of constraints $\mathscr{H}$. Selecting
    uniformly at random, a virtual copy of element $x$ is selected
    with probability $\frac{w_x}{\sum_{h \in \mathscr{H}} w_h}$, which
    is precisely the same as the probability that $x$ is selected when
    sampling with weighted probabilities.
    
    Let $m = \abs{\mathscr{H}} = \sum_{h \in \mathscr{H}} w_h$, i.e.
    the total weight. Applying the result above, the expected number
    of constraints in $\mathscr{H}$ that violate a uniform random
    sample of $r$ constraints is $\frac{d (m - r + 1)}{r - d}$. Since
    $r - 1$ is always positive, we can add $r - 1$ to the numerator to
    achieve a looser bound of $\frac{d }{r - d}m$.
    
    Now we convert our results back from the ``virtual copies'' case
    back to the non-uniform weighted sampling case. $m$ is the total
    weight. Note that either all virtual copies of a constraint are
    satisfied or none are, since they are all the same. So if a
    constraint is violated, it appears in the set of violators with
    multiplicity proportional to its weight; thus, the expected size
    of the set of violators in the uniform case is the expected weight
    of the violators in the weighted-sampling case. We showed that
    this is at most $\frac{d}{r-d} m$ above, which is a $\frac{d}{r-d}$
    fraction of the total weight.
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      Consider any three non-collinear points. By definition, the
      circumcenter of the triangle defined by the three points is
      equidistant from the points. It is found at the intersection of
      the perpendicular bisectors of the lines connecting each of the
      two pairs of points; because they are not collinear, they have a
      unique intersection point. This can be computed in constant time
      by computing the midpoints of the edges, the angle perpendicular
      to them, and the intersection of the three lines thus produced.
    \end{subproblem}

    \begin{subproblem}
      By definition of the general position, $\mathscr{O}(H)$ cannot contain
      four or more points on the boundary of a circle. Call its radius
      $r$. If it has no input points on its boundary, then let $k$ be
      the distance from its center to the farthest point; since $\mathscr{O}(H)$
      contains all points in $H$, $r > k$, and since the concentric
      circle with radius $k$ also contains all points in $H$, this
      contradicts the optimality of $\mathscr{O}(H)$. So suppose $\mathscr{O}(H)$ has one
      input point $x$ on its boundary. Note that if we move the center
      towards $x$ by $\delta$ and decrease the radius by $\delta$,
      we obtain a smaller circle that still has $x$ on its
      boundary. Since $x$ is the only point on the boundary, there
      must be some smallest value of $\delta$ that puts another
      point on the boundary; if we move the center towards $x$ by some
      $\epsilon < \delta$ and decrease the radius to $r - \epsilon$,
      we obtain a smaller circle that still contains every point in
      $H$, contradicting the optimality of $\mathscr{O}(H)$. So $\mathscr{O}(H)$ must have
      either two or three points on its boundary.
      
      Moreover, we claim that if $\mathscr{O}(H)$ has two points on its
      boundary, they are on the diameter of the circle. Assume the
      contrary. Then consider the chord between the two points on the
      diameter. Using the same idea as above, we must be able to move
      the center infinitesimally closer to the chord while decreasing
      the radius accordingly to keep the two points on the boundary of
      the circle. This contradicts the optimality by giving a smaller
      circle containing all the points.

      This gives a $\bigO{n^4}$ algorithm for finding $\mathscr{O}(S)$. $\mathscr{O}(S)$
      is therefore uniquely defined by a basis of either two points on
      the diameter, of which there are $\bigO{n^2}$ such
      configurations, or three points, of which there are
      $\bigO{n^3}$. It is easy to find the center and radius and check
      that every point in the set is within the appropriate distance
      of the center in $\bigO{n}$ time, so checking each possible
      assignment requires $\bigO{n^4}$ time.
    \end{subproblem}

    \begin{subproblem}
      Suppose $C$ is the smallest circle containing $B(H)$. We show
      that it does not exclude any point in $H$. Assume the
      contrary, that there is some $p \in H$ not enclosed in $C$. Then
      $C$ cannot be $\mathscr{O}(H)$. There are two cases: either it has the
      same center as $\mathscr{O}(H)$, or it does not. The former case violates
      the definition of $B(H)$: $\mathscr{O}(H)$ is concentric with $C$ but
      contains some point not in $C$, so must be larger, but then the
      points in $B(H)$ cannot be on the boundary of $\mathscr{O}(H)$. In the
      second case, $C$ and $\mathscr{O}(H)$ have distinct centers. In the same
      way as above, we can move the center of $\mathscr{O}(H)$ infinitesimally
      closer to the center of $C$ and shrink the radius accordingly,
      creating a smaller circle that still has $B(H)$ on its
      boundary without excluding any further points. This contradicts
      the optimality of $\mathscr{O}(H)$.
    \end{subproblem}

    \begin{subproblem}
      \def\SUP{S \cup \set{p}} Suppose $p$ is not contained in $\mathscr{O}(S)$
      for some $S$, and $p$ is not on the boundary of $\mathscr{O}(\SUP)$. Then
      the boundary $B(\SUP)$ must consist entirely of points in
      $\mathscr{O}(S)$. The smallest circle $\mathscr{O}(B(\SUP))$ enclosing $B(\SUP)$
      therefore must be at least as small as the smallest circle
      $\mathscr{O}(S)$ enclosing all points in $S$. But the previous subproblem
      shows that $\SUP$ must be contained within $\mathscr{O}(B(\SUP)$. $\SUP$
      contains a point $p$ not in $\mathscr{O}(S)$, so $\mathscr{O}(\SUP)$ must be
      strictly larger than $\mathscr{O}(S)$, and therefore $\mathscr{O}(B(\SUP))$ must be
      as well. This contradicts the fact that it is at least as small
      as $\mathscr{O}(S)$. So $p$ must be on the boundary of $\mathscr{O}(\SUP)$. 
    \end{subproblem}

    \begin{subproblem}
      We bound the expected number of points in $H$ outside $\mathscr{O}(R)$ in
      the same way as bounding the number of violating constraints in
      the linear programming algorithm. Define $\mathscr{C}_H$ to be
      the set of bases of all subsets of the set of points:
      $\mathscr{C}_H = \set{B(T) | T \subseteq H}$. Now for any
      particular $x \in \mathscr{C}_H$, define $v_x$ to be the
      number of points in $H$ outside $\mathscr{O}(x)$, and $i_x$ to be 1 if $x
      = B(R)$ and 0 otherwise. Then
      \[ \Exp{\abs{V}}=\Exp{\sum_{x \in \mathscr{C}_H} v_xi_x} =
      \sum_{x \in \mathscr{C}_H} v_x \Pr{i_x} \]
      
      We now analyze $\Pr{i_x}$. $i_x$ equals 1 precisely when $x$ is
      the basis of $R$, or every point in $R$ is in $\mathscr{O}(x)$. For this
      to occur, the $\abs{x}$ elements in $x$ must be contained in
      $R$, and the other $r-\abs{x}$ elements must be chosen from the
      $n - v_x - \abs{x}$ other elements that are within $\mathscr{O}(x)$. This
      gives
      \[ \Pr{i_x} = \frac{ \binom{n - v_x - \abs{x}}{r -
          \abs{x}}}{ \binom{n}{r} } \]
      We can (thankfully!) appeal to the analysis from class to bound
      this sum: now $n$ takes the place of $m$, and $\abs{x}$ that of
      $q_x$. So
      \[ \Exp{\abs{V}} \le \frac{n - r + 1}{r - \abs{x}} \abs{x} \]
      Since $x$ is a basis, $\abs{x}$ is either 2 or 3, and so
      \[ \Exp{\abs{V}} \le \frac{3\left(n - r + 1\right)}{r - 2}  \]
    \end{subproblem}

    \begin{subproblem}
      Now fix $S \subseteq H$ and consider the number of points in $H$
      outside $\mathscr{O}(R \cup S)$. This time, define $\mathscr{C}_H =
      \set{B(T \cup S) | T \subseteq H \setminus S}$. Define $v_x$ and
      $i_x$ in the obvious way: $v_x$ is the number of points in $H$
      outside $\mathscr{O}(x \cup S)$, and $i_x$ is 1 iff $x \cup S$ is the
      basis of $R$. Then we obtain the same equation as before:
      \[ \Exp{\abs{V}}=\Exp{\sum_{x \in \mathscr{C}_H} v_xi_x} =
      \sum_{x \in \mathscr{C}_H} v_x \Pr{i_x} \]

      The analysis of $\Pr{i_x}$ is slightly different: now $x \union S$ must
      be the basis of $R \cup S$, i.e. every point in $R \cup S$ must
      be in $x \union S$. This is the same as before, except that now
      the elements in $S$ are necessarily in the set $R \union S$. So
      from the $n$ elements, $R$ must contain those in $x \setminus
      S$; the other $r - \abs{x \setminus S}$ must be chosen from the
      $n - v_x - \abs{x \setminus S}$ other elements in $\mathscr{O}(x)$. So
      \[ \Pr{i_x} = \frac{ \binom{n - v_x - \abs{x \setminus S}}{r -
          \abs{x \setminus S}}}{ \binom{n}{r} } \]
      and so
      \[ \Exp{\abs{V}} \le \frac{n - r + 1}{r - \abs{x\setminus S}}
      \abs{x \setminus S } \le \frac{3\left(n - r + 1\right)}{r}
      \]
    \end{subproblem}

    \begin{subproblem}
      Now we can find $\mathscr{O}(H)$ using an algorithm similar to
      $\proc{SampLP}$. If the number of points is less than some fixed
      constant $k$, we solve the problem in $\bigO{n^4}$ using the
      algorithm above. Otherwise, we maintain an active set $S$
      (initially empty). We randomly sample the set of points,
      choosing a subset of size $3 \sqrt{n}$, and recursively apply
      our algorithm to this sample. Call its return value $x$. We
      identify the set $V$ of points that are not contained within
      $\mathscr{O}(x)$, and add them to the active set if there are less than $2
      \sqrt{n}$ of them. We repeat this process until there are no
      vertices in $V$, in which case $x$ is the optimum.

      Using the bound from above and the Markov inequality, for any
      random sample, $\Pr{\abs{V} \ge 2\sqrt{n}} \le \nicefrac12$, so
      the expected number of iterations between augmentations of $S$
      is at most 2. Each augmentation of $S$ must add one of the
      points in $\mathscr{O}(S)$, so there are at most 3 augmentations before
      $V$ becomes empty. So the algorithm makes 6 recursive calls in
      expectation, and each has subproblem size at most $6 \sqrt{n}$
      (since each augmentation adds at most $2 \sqrt{n}$ points). So
      \[ T(n) = 6 T(6 \sqrt{n}) + \bigO{n} = \bigOt{n} \]
    \end{subproblem}
  \end{problem}
\end{pset}
\end{document}