Homework10-2.tex

\section{0423}\label{sec:0423}
\begin{questions}

    \question 给定平面上一组点，已知每个点的坐标，求最远点对之间的距离，即点集的直径。
    （不得穷举，文献查阅，然后用自己的语言进行算法思想的描述，包括时间复杂性分析）

    \begin{solution}
        \textit{
            \href{http://euro.ecom.cmu.edu/people/faculty/mshamos/1978ShamosThesis.pdf}
            {Shamos M I. Computational geometry[Ph. D. Thesis][J]. 1978.}
        }

        \textsf{引理\quad}最远点对一定在这组点的凸包上。

        \begin{proof}
            反证法。
            假设最远点对为$(p,q)$，其中$q$不在这组点的凸包上，则根据凸包的定义$q$一定在凸包的内部。
            对凸包多边形进行三角形分划，一定能找到\begin{itemize}
                \item {
                      凸包上一点$x$，使点$q$在线段$px$上。
                      此时一定有$d_{px} > d_{pq}$，即$pq$不是最远点对。
                      }
                \item {
                      或凸包上的两点$x,y$，使点$q$在$\triangle pxy$的内部。

                      因为三角形内角和为$180^\circ$，
                      所以在$\triangle qxy$中，$\angle xqy < 180^\circ$，
                      所以$\angle pqx + \angle yqp > 180^\circ$。
                      不妨设$\angle pqx \le \angle yqp$，则有$2 \angle yqp > 180^\circ$，
                      即$\angle yqp > 90^\circ$。

                      所以在$\triangle yqp$中，$\angle yqp$是最大的角，$\angle yqp > \angle pyq$。
                      由正弦定理，$d_{yp} > d_{pq}$，所以$pq$不是最远点对。
                      }
            \end{itemize}
            因此最远点对一定都在这组点的凸包上。
        \end{proof}
        应用Graham扫描算法可以找到这组点的凸包，时间复杂度为$O(n \log n)$

        作凸多边形两条平行的支撑线，并沿逆时针方向同时旋转两条平行支撑线。
        则若凸包上两点是最远点对，一定存在某一时刻，使两点均在平行线上。
        因此在旋转的过程中求出能同时出现在两平行线上的点对之间的距离，并找到最大值即可。

        因为两条支撑线将共同遍历全部的点一次，所以算法的时间复杂度为$O(n)$。

        总的时间复杂度为$O(n \log n)$
    \end{solution}

    \question 给定测度空间中位于同一平面的$n$个点，已知任意两点之间的距离$d_{ij}$，存储在矩阵$D$中，求这组点的直径。

    该问题的直观解法就是把$D$扫描一遍，选择其中最大的元素即可。
    由于是在一个测度空间中，因此$d_{ij}$满足距离的基本要求，即非负性、对称性和三角不等式。
    我们就可以给出一种时间亚线性的近似算法。
    算法很简单，由原来确定性算法的检查整个矩阵改为只随机检查$D$的某一行，
    这样时间复杂性就由原来的$O(n^2)$减少为$O(n)$。
    相对于输入规模$n^2$而言，这是一个时间亚线性的算法。
    那么时间代价减小的同时，证明解不会小于最优值的一半。

    \begin{solution}
        % 即证：平面上$n$个点中，$\exists (x,y) : \forall (i,j) \ne (x,y) , d_{ij} \le d_{xy}$。
        % 则对平面上任意一点$a$，

        \proof 记$(p,q)$为平面上最远点对，即$d_{pq}$为该点集的直径。

        在矩阵$D$中任取一行，即在平面上任取一点$x$，考察$x$与平面上其他点的距离。
        \begin{itemize}
            \item 若$x = p \vee x = q$，则$d_{pq}$一定在选定的这一行中，所得解即为最优值。
            \item 若$x \ne p \wedge x \ne q$，则$d_{xp}, d_{xq}$一定在选定的这一行中。
                  \begin{itemize}
                      \item 若$x,p,q$共线，则有$d_{xp} + d_{xq} = d_{pq}$
                      \item 若$x,p,q$不共线，则三点构成平面上的一个三角形，有$d_{xp} + d_{xq} > d_{pq}$
                  \end{itemize}
                  即$d_{xp} + d_{xq} \ge d_{pq}$。
                  不妨设$d_{xp} \le d_{xq} \le d_{pq}$，\[
                      d_{pq} \le d_{xp} + d_{xq} \le 2d_{xq} \Longrightarrow
                      d_{xq} \ge \frac{1}{2} d_{pq}
                  \]
                  设选定的这一行中最大的距离（即算法的输出）为$d_{xy}$，则\[
                      d_{xy} \ge d_{xq} \ge \frac{1}{2}  d_{pq}
                  \]
        \end{itemize}
    \end{solution}

    \question 在平面上给定一个有$n$个点的集合$S$，求$S$的极大点。

    极大点的定义：设$p_1=(x_1,y_1)$和$p_2=(x_2,y_2)$是平面上的两个点，
    如果$x_1 \le x_2$并且$y_1 \le y_2$，则称$p_2$支配$p_1$，记为$p_1 \prec p_2$。
    点集$S$中的点$p$为极大点，意味着在$S$中找不到一个点$q$，$q \ne p$并且$p \prec q$，
    即$p$不被$S$中其它点支配。

    \begin{solution}

        \begin{algorithm}[H]
            \caption{求平面的极大点}
            \begin{algorithmic}[1]
                \Require { $S = \left\{ (x_i, y_i) \right\}$（平面上的$n$个点） }
                \Ensure { $P = \left\{ (x_i, y_i) \right\}$（平面上所有的极大点） }
                \State $S \gets \Call{Sort}{S, x, \mathsf{descending}}$ \Comment{对横坐标降序排序，$O(n \log n)$}
                \State $maxY \gets - \infty$
                \For {$(x,y)$ in $S$} \Comment{按横坐标降序遍历}
                \If {$ y > maxY $} \Comment{横坐标大于$x$的点纵坐标都小于$y$，没有其他点可以支配该点}
                \State $P \gets P \cup \left\{ (x,y) \right\}$
                \State $maxY \gets y$
                \Else
                \Statex \Comment{该点被之前遍历过的某个纵坐标为$maxY$的点支配}
                \EndIf
                \EndFor
            \end{algorithmic}
        \end{algorithm}

    \end{solution}

\end{questions}