Homework SoursehttpswwwcheggcomhomeworkhelpIntroductiontoJavaProgrammingCom
https://www.chegg.com/homework-help/Introduction-to-Java-Programming-Comprehensive-Version-10th-edition-chapter-22-problem-7PE-solution-9780133761641
The above link goes to the text book question without a solution to better help explain the problem.
use an algorithim for find the closest pair of points using a divide and conquer approach. It needs to implement four different methods that are outlined in the above links text book question.
Thank you for the help!!
Solution
Steps in the Algorithm as listed below -
(using a divide and conquer approach)
1) Find the middle point in the sorted array, say P[n/2] as middle point.
// Define a class named Point.
2) By dividing the given array in two halves, the first subarray contains points from P[0] to P[n/2]. The second subarray contains points from P[n/2+1] to P[n-1].
// Class Point with 2 data fields x and y co-ordinates.
3) Find the smallest distances in both subarrays, recursively. Let the distances be distleft and distright. Find the minimum of distlrft and distright. Let the minimum distance be d.
//Define class with data fields p1 and p2 (distleft and distright).
4) From above 3 steps, we can know that there is an upper bound d of minimum distance.
So, we need to consider the pairs such that one point in pair is from left half and other is from right half.
Consider the vertical line passing through P[n/2] and find all points whose x coordinate is closer than d to the middle vertical line. Build an array s[] of all such points.
5) We need to sort the array s[] according to y coordinates. This step is O(nLogn). It can be optimized to O(n) by sorting and merging recursively.
6) Find the smallest distance in s[]. From first look, it seems to be a O(n^2) step, but it is actually O(n). It can be proved geometrically that for every point in the strip, we only need to check at most 7 points after it 7) At last, return the minimum of d and distance calculated in above step i.e (step 6)
Implementation (in Java (program))-
public class PairClose
{
private Point2D b1, b2;
private double theDistance = Double.POSITIVE_INFINITY;
public PairClose(Point2D[] points) //public static Pair getClosestPair(double [][]points)
{
int n = points.length;
if (n <= 1) return;
Point2D[] pointsByX = new Point2D[n]; // sorting the co-ordinates
for (int i = 0; i < n; i++)
pointsByX[i] = points[i];
Arrays.sort(pointsByX, Point2D.X_ORDER);
for (int i = 0; i < n-1; i++) {
if (pointsByX[i].equals(pointsByX[i+1])) {
theDistance = 0.0;
b1 = pointsByX[i];
b2 = pointsByX[i+1];
return;
}
}
)
Point2D[] pointsByY = new Point2D[n];
//to sort by the co-ordiante y but not yet sorted
for (int i = 0; i < n; i++)
pointsByY[i] = pointsByX[i];
Point2D[] aux = new Point2D[n];
c1(pointsByX, pointsByY, aux, 0, n-1);
}
private double c1(Point2D[] pointsByX, Point2D[] pointsByY, Point2D[] aux, int lo, int hi) {
if (hi <= lo) return Double.POSITIVE_INFINITY;
int mid = lo + (hi - lo) / 2;
Point2D median = pointsByX[mid];
//Compute result with endpoints of left and right subarray
double d1 = c1(pointsByX, pointsByY, aux, lo, mid);
double d2 = c1(pointsByX, pointsByY, aux, mid+1, hi);
double d = Math.min(d1, d2);
merge(pointsByY, aux, lo, mid, hi);
//merge and sort by y co-ordinate
int m = 0;
for (int i = lo; i <= hi; i++) {
if (Math.abs(pointsByY[i].x() - median.x()) < d)
aux[m++] = pointsByY[i];
}
for (int i = 0; i < m; i++) {
for (int j = i+1; (j < m) && (aux[j].y() - aux[i].y() < d); j++) {
double distance = aux[i].distanceTo(aux[j]);
if (distance < d) {
d = distance;
if (distance < theDistance) {
theDistance = d;
b1 = aux[i];
b2 = aux[j];
}
}
}
}
return d1; // return one of the data in the points
}
public Point2D either() {
return b1;
}
* @return
//Returns the other points
public Point2D other() {
return b2;
}
public double distance() {
return theDistance;
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi)
//they are sorted subarrays
{
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public static void main(String[] args) {
int n = StdIn.readInt();
Point2D[] points = new Point2D[n];
for (int i = 0; i < n; i++) {
double x = StdIn.readDouble();
double y = StdIn.readDouble();
points[i] = new Point2D(x, y);
}
PairClose c1 = new PairClose(points);
StdOut.println(c1.distance() + \" from \" + c1.either() + \" to \" + c1.other());
}}
