Introduction

These are a type of algorithms used to solve computational geometry problems. In these problems, we have to find such a pair of points that the distances between them is smallest compared to the distance between other points residing in a metric space (a set having defined distance for all elements in it). Algorithms dealing with this type mainly follow the Divide-and-Conquer strategy. Generally, the algorithms require O (n2) time to solve these type of problems but under special circumstances, it can be reduced to O (n (log n)).

Problem

We have to find the closest pair of points among a set Q of points with at least two elements (n ? 2). Here, by the term “closest” we meant a Euclidean distance. The smallest possible value we can achieve is zero and this would only happen when both points are coincident.

Solution

One possible way to solve this problem is by using a brute force algorithm. This is done by using to calculate the distance between two points P1 (x1, y1) and P2 (x2, y2). This step is performed on all possible pairs of points and then the minimum value of the distance is taken. Brute Force, in this case, has worst-case time as ? (n2). This can be reduced to O (n (log n)) times by using divide-and-conquer strategy and recursion.

Divide-and-Conquer

Every time a recursive call is made, a subset P of the set Q is taken along with arrays X and Y, having all points of subset P. The points in X are sorted in monotonically (either entirely increasing or decreasing) increasing order according to x-coordinate. Similarly, in Y points are stored in monotonically increasing y-coordinate. In order to achieve O (n (log n)), we cannot perform sort in each recursive call. For this purpose, we use presorting to avoid sorting every time a recursive call is made.

When a recursion is made, first of all, it is checked whether |P| ? 3. If this condition is true then brute-force method is called two times else the following steps are called recursively.

Divide

then brute

Applications

· Traffic Control Systems