$2$ Problem Statement

The Closest Pair Problem is a classical computational geometry problem that aims to find the two closest points in a set of $n$ points in a $2-$dimensional plane. In this project, students will implement and compare two approaches for solving the closest pair problem: Brute force and Divide$-$and$-$conquer. The task involves analyzing the performance of these methods across randomly generated datasets of varying sizes. Students are encouraged to use any programming language of their choice, with the requirements listed below.

$2\mathrm{.}1$ Implementation Requirements

Implement the brute$-$force and divide$-$and$-$conquer approaches for the closest pair problem.

You may use standard libraries for basic operations such as sorting and computing the Euclidean distance between two points $($Do not use any specialized libraries or built$-$in functions that directly solve the closest pair problem.$).$

Other than these helper libraries, you should implement and submit your own work.

$2\mathrm{.}2$ Performance Analysis

Evaluate the performance of both approaches using datasets of increasing size $($e$.$g$.,n=100,500,1000,10K,100K,1M.$

Measure and compare the runtime of both methods for each dataset size.

Use figures to illustrate how the performance changes with dataset size for both algorithms.

$1$

Theoretically analyze and compare the time complexity of the two algorithms. Compare the theoretical analysis with the experimental results.