Question $4(35$ points$)$

You are given a set of n points on a $2$D plane, where each point is represented

as a pair of coordinates $($x$,$ y$).$ our task is to design an algorithm that finds the

closest pair of points. The distance between two points $($x$1,$ y$1)$ and $($x$2,$ y$2)$ is

given by the Euclidean distance formula:

d$(($x$1,$ y$1),($x$2,$ y$2))=$ p

$($x$1$ x$2)$

$2+($y$1$ y$2)$

$2$

Objective:

Design an efficient algorithm to solve this problem using the Divide and Conquer

approach. The goal is to achieve a time complexity of O$($n log n$).$

Input: A list of n points, where each point is represented as a tuple $($x$,$ y$)$ and

n $>=2$

Output: The closest pair of points and the distance between them.

Approach:

$$ Divide: Split the set of points into two halves based on their x$-$coordinates.

$$ Conquer: Recursively find the closest pair of points in each half.

$$ Combine: After finding the closest pair in each half, check if there exists

a closer pair of points that straddles the dividing line between the two

halves.

Subtasks

$$ Sorting: First, sort the points based on their x$-$coordinates and y$-$coordinates.

Explain how sorting helps in efficiently finding the closest pair. $(5$ points$)$

$$ Recursive Closest Pair: Write a recursive function that splits the problem

and calls itself on each half. Write a pseudo$-$code or actual code for this

step. $(10$ points$)$

$$ Strip Check: After the recursion step, check a small $$strip$$ region near

the dividing line for possible closer pairs. Write a pseudo$-$code or actual

code for this step. Also, explain why only a few points need to be checked

in this region. $(10$ points$)$

$$ Base Case: Define the base case when the number of points is small $($e$.$g$.,$

$2$ or $3$ points$).$ Explain how you solve it$.(5$ points$)$

Performance Analysis

$$ Derive the time complexity of your algorithm and explain why the algorithm runs in O$($nlogn$)$ time. $(5$ points$)$