# 3 - Geometric 3 Flashcards

1
Q

What is the closest pair of points problem?

A

Given a set P of n points in a plane, find a pair whose distance from each other is as small as possible

2
Q

What is the naive approach to the closest pair problem?

A

Check each pair which is O(n2) complexity

3
Q

What is the best approach for the closest pair problem?

A

Divide and conquer algorithm O(n log n) complexity Based on sorting

4
Q

What is an example of a divide and conquer algorithm?

A

Merge sort

5
Q

What is the merge sort algorithm? (code)

A

int [] a = {…}; public void mergeSort(int i, k) { if (i

6
Q

What is the merge algorithm/code?

A

/** 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]; }

7
Q

Analysis of mergeSort

A

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)

8
Q

What is the idea of the closest pair algorithm?

A

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

9
Q

How to solve case iii of closest pair algorithm?

A

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

10
Q

How to sort points in the strip by ycoord?

A

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

11
Q

What is the closest pair algorithm (code)?

A

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

12
Q

Required subsidiary methods for closest pair algorithm

A

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 */

13
Q

How to return an actual closest pair of points?

A

Every time d is updated, store the two points s[a] and s[b] that were responsible for the update being made

14
Q

Analysis of closest pair algorithm

A

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)