3 - Geometric 3 Flashcards
What is the closest pair of points problem?
Given a set P of n points in a plane, find a pair whose distance from each other is as small as possible
What is the naive approach to the closest pair problem?
Check each pair which is O(n2) complexity
What is the best approach for the closest pair problem?
Divide and conquer algorithm O(n log n) complexity Based on sorting
What is an example of a divide and conquer algorithm?
Merge sort
What is the merge sort algorithm? (code)
int [] a = {…}; public void mergeSort(int i, k) { if (i
What is the merge algorithm/code?
/** Merges sorted segments a[i..j] and * a[j+1..k] to give a[i..k] sorted */ private void merge(int i, int j, int k) { int index1, index2, index3; int [] temp = new int[a.length]; index1 = i; index2 = j+1; index3 = i; while ( index1 j && index2 k ) if (a[index1] a[index2]) temp[index3++] = a[index1++]; else temp[index3++] = a[index2++]; if ( index1 j ) temp[index3..k] = a[index1..j]; else if ( index2 k ) temp[index3..k] = a[index2..k]; a[i..k] = temp[i..k]; }
Analysis of mergeSort
Let f(n) be worst-case complexity, then f(n) 1) f(1) = d where c and d are constants n/2 is resurcive calls, cn is merge Solving the recurrence relation: Assume n = 2ᵏ for simplicity, so k = log₂n f(n)
What is the idea of the closest pair algorithm?
Sort P by xcoord once at the outset Divide P into 2 equal sized subsets Q and R, based on xcoord Solve for each subset recursively Combine: closest pair(x,y) satisfies either: i) x∈Q, y∈Q (solved already) or ii) x∈R, y∈R (solved already) or iii) x∈Q, y∈R (distance apart
How to solve case iii of closest pair algorithm?
Case iii = x∈Q, y∈R (distance apart d from L - (worst cause might not eliminate any) If we sort remaining points on ycoord, any such point can be at distance
How to sort points in the strip by ycoord?
Sort all points in strip in increasing order of ycoord If we do this everytime we “combine” it leads to O(n log²n) algorithm - can do better Trick: mimic mergesort: - Assume that the points in Q are sorted in increasing order of y-coordinate (when we solve Closest Pair on Q) - Assume that the points in R are sorted in increasing order of y-coordinate (when we solve Closest Pair on R) - At the “Combine” step, merge the two sorted sets to get all points in the strip sorted in increasing order of y-coordinate This leads to a faster algorithm
What is the closest pair algorithm (code)?
public double closestPair(PointSet p) { /** Input: a PointSet p * Output: d, the distance between * the closest pair of points in p */ sortOnXCoord(p); // sort points in p on x-coordinate return cPRec(p, 0, p.length-1); } private double cPRec (PointSet p, int i, int k) { /** assumes p[i..k] sorted on x-coordinate; * returns the distance between a * closest pair of points in p[i..k]; * also returns, in p[i..k], the points * initially in p[i..k] sorted on y coordinate */ double d; if (i == k) d = Double.MAX_VALUE; else { int j = (i+k)/2; // mid-point of p[i..k] double mid =(p[j].x + p[j+1].x))/2.0; // x coord of mid-line double d1 = cPRec(p, i, j); // p[i..j] sorted on y coord double d2 = cPRec(p, j+1, k); // p[j+1..k] sorted on y coord merge(p, i, j, k); // p[i..k] sorted on y coord d = Math.min(d1, d2); PointSet s = filter(p, i, k, d, mid); // the points in the “strip” int m = s.length; // no. of points in s for (int a=0; a
Required subsidiary methods for closest pair algorithm
private PointSet filter(PointSet p, int i, int k, double d, double z); /** returns a PointSet containing points in p[i..k] with * x-coord within d of z; preserves relative order */ private double dist(Point2D.Double a, Point2D.Double b) /** returns the distance between the points a and b */
How to return an actual closest pair of points?
Every time d is updated, store the two points s[a] and s[b] that were responsible for the update being made
Analysis of closest pair algorithm
Initial sort on x-coordinate is O(n log n) When dealing with an array of length n, merge and filter are both O(n) The nested for loops contribute O(n) - the outer loop is executed m ( 1) f(1) = d where c and d are constants. So f(n) = O(n log n) (as for Mergesort)
