Closest Pair Problem

$1$ Objectives

By completing this project, students will:

$$ Gain practical experience in implementing algorithmic solutions for computational ge$-$

ometry problems.

$$ Understand the trade$-$offs between brute$-$force and divide$-$and$-$conquer approaches.

$$ Learn to analyze and interpret the computational complexity of algorithms.

$$ Develop skills in data visualization and technical reporting.

$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 prob$-$

lem.

$$ 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,10$K$,100$K$,1$M$).$

$$ 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 algo$-$

rithms.

$1$ Theoretically analyze and compare the time complexity of the two algorithms. Com$-$

pare the theoretical analysis with the experimental results.

$2\mathrm{.}3$ Report Guidelines

Students are required to provide a detailed report containing:

$$ A brief introduction to the problem.

$$ Pseudocode for both approaches.

$$ Theoretical analysis of the computational complexity between the two methods.

$$ Figures and charts showing the performance analysis.

$$ Conclusions drawn from the results.

$$ Names of team members $($maximum $3)$ and contribution of each member.

$$ Cite any external resources used, such as textbooks, websites, or research papers.

$2\mathrm{.}4$ Deliverables

$1.$ A PDF document containing all the sections outlined in the report guidelines.

$2.$ All source code files $($in a zipped file$),$ well$-$organized and commented.

$3.$ A README or metadata file with instructions on how to compile and run your pro$-$

grams, including any necessary installations or dependencies.

$3$ Optional Bonus

$3\mathrm{.}1$ Testing on the World Cities Dataset $(3\%)$

As an optional bonus, students are encouraged to test their implemented algorithms on a

real$-$world dataset: the World Cities Dataset. In this dataset, the latitude and longitude

of cities around the world are used as the coordinates for the closest pair problem.

$3\mathrm{.}1\mathrm{.}1$ Requirements

$$ Use the World Cities Dataset available on Kaggle, which contains the names, countries,

and geographical coordinates of cities worldwide.

$$ Treat the latitude and longitude as the x and y coordinates respectively, and compute

the closest pair of cities using both the brute force and divide$-$and$-$conquer approaches.

$$ Compare the performance of the two algorithms for varying subsets of the dataset

$($based on cities within a $($a$)$ specific region, $($b$)$ country, $($c$)$ the entire dataset$).$

$2$ Provide a detailed analysis in the report, including:

$$ A description of the dataset.

$$ Figures and charts showing the runtime comparison between the two approaches.

$$ Discussion of the challenges $($if any$)$ encountered during this task.

$3\mathrm{.}2$ Implementing the Sweep Line Algorithm $(2\%)$

For an additional bonus, students are encouraged to implement the Sweep Line algorithm for solving the closest pair problem iteratively.

$3\mathrm{.}2\mathrm{.}1$ Requirements

$$ Implement the iterative Sweep Line algorithm for the closest pair problem.

$$ Add this algorithm to the experimental analysis alongside the brute$-$force and divide$-$and$-$conquer approaches.

$$ Add the pseudocode of this algorithm to your report.

$$ Compare the performance of all three algorithms $($brute force, divide$-$and$-$conquer, and sweep line$)$ both theoretically and experimentally.