Closest Pair - Question 6 Answers

$$ \def\hl\{\bbox[yellow]} \def\constant\{\enclose{circle}[mathcolor="blue"]} \def\term\{\enclose{circle}[mathcolor="green"]} \def\blueci\{\enclose{circle}[mathcolor="blue"]} \def\greenci\{\enclose{circle}[mathcolor="green"]} \def\orangeci\{\enclose{circle}[mathcolor="orange"]} \def\U\{\mathbb{U}} \def\N\{\mathbb{N}} \def\Z\{\mathbb{Z}} \def\Q\{\mathbb{Q}} \def\R\{\mathbb{R}} \newcommand{\green}[1]{\textcolor{green}{#1}} \newcommand{\blue}[1]{\textcolor{blue}{#1}} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\card}[1]{\lvert #1 \rvert} $$


Replace lines 20 thru 32 in the pseudo code with the code below to remove the no duplicate x value constraint.

\caption{Closest Points With Duplicate x Values}
    \STATE \COMMENT{Notice that we now defining the divide by the entire point, not just the x value}
    \STATE divide $\gets Ax_{\text{mid -1}}$
    \STATE left-y $\gets \emptyset$
    \STATE right-y $\gets \emptyset$
    \FOR{$i \in Ay$}
        \STATE \COMMENT{If x is equal to the divide, split on the y value}
        \IF{i.x = divide.x}
            \IF{$i.y \leq$ divide.y}
                \STATE left-y $\gets \text{left-y} \cup \{i\}$
                \STATE right-y $\gets \text{right-y} \cup \{i\}$
        \ELSEIF{$i.x \leq$ divide.x}
            \STATE left-y $\gets \text{left-y} \cup \{i\}$
            \STATE right-y $\gets \text{right-y} \cup \{i\}$

Additionally, the reference to divide on line 43 must change to divide.x.

Return to Exercises