Design and Analysis of Algorithm
  • Design and Analysis of Algorithm
  • Divide and Conquer Technique
    • Merge Sort
    • Quick sort
    • Maximum Sum Contiguous Subsequence
    • Comparison Between Quick Sort & Merge sort
    • Closest Pair of Points
  • Backtracking
  • Tutorial
    • Week - 1
    • Week - 2
    • Week - 3
    • Week - 4
    • Week - 5
Powered by GitBook
On this page

Was this helpful?

  1. Divide and Conquer Technique

Closest Pair of Points

Very important Problem in Computational Geometry!!

PreviousComparison Between Quick Sort & Merge sortNextBacktracking

Last updated 5 years ago

Was this helpful?

Problem Definition: Given a set of n points, find the closest pair of points. Points with least distance.

Distance between pair of points (x,y) and (z,w) are computed using euclidean distance which is given as follows: distance=(x−z)2+(y−w)2distance = \sqrt{(x-z)^{2} +(y-w)^{2} }distance=(x−z)2+(y−w)2​

Brute-force approach could be finding the distance between every pair of points and identifying the pair with shortest distance.

Closest pair of points