NUMERIC & GEOMETRIC ALGORITHMS

Numeric and geometric algorithms are two broad categories of algorithms that deal with numerical data and geometric shapes, respectively. Here's an overview of each:

Numeric algorithms: Numeric algorithms are mathematical algorithms that are designed to solve problems related to numbers and numerical data. These algorithms can be used to perform operations such as addition, subtraction, multiplication, division, and exponentiation on numbers, as well as to calculate numerical solutions to equations and perform statistical analysis on data. Examples of numeric algorithms include sorting algorithms like quicksort and mergesort, as well as optimization algorithms like linear programming and gradient descent.

Geometric algorithms: Geometric algorithms are mathematical algorithms that are designed to solve problems related to geometric shapes, such as points, lines, planes, and polygons. These algorithms can be used to perform operations such as finding the distance between two points, calculating the area of a polygon, and determining whether a point lies inside or outside a given shape. Examples of geometric algorithms include collision detection algorithms used in computer graphics and game development, as well as algorithms used in geographic information systems (GIS) to analyze and manipulate spatial data.

It's worth noting that some algorithms can fall into both categories. For example, the fast Fourier transform (FFT) is a numerical algorithm used to perform efficient signal processing, but it also has applications in geometric algorithms for shape recognition and image processing.

EUCLID’S ALGORITHM

Euclid's algorithm is a mathematical algorithm used to find the greatest common divisor (GCD) of two integers. The GCD is the largest positive integer that divides both integers without a remainder.

The algorithm works by repeatedly subtracting the smaller integer from the larger integer until one of the numbers becomes zero. The GCD is then the remaining non-zero number.

Here is an example of how Euclid's algorithm can be used to find the GCD of two integers:

Let's say we want to find the GCD of 60 and 48.

First, we divide the larger number (60) by the smaller number (48), and find the remainder (12): 60 = 48 * 1 + 12
Next, we divide the smaller number (48) by the remainder (12), and find the new remainder (0): 48 = 12 * 4 + 0
Since the remainder is now 0, we stop. The GCD of 60 and 48 is the last non-zero remainder we found, which is 12.

The algorithm can be implemented recursively or iteratively, and has a time complexity of O(log n), where n is the larger of the two input numbers.

Here is an example implementation of Euclid's algorithm in Java:


public static int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

In this implementation, the gcd method takes two integers a and b as input and returns their GCD using Euclid's algorithm. The method checks if b is zero, in which case the GCD is a. Otherwise, it calls itself recursively with b as the new value of a and a % b as the new value of b. This continues until b is zero and the GCD is found.

CONVEX HULL & GRAHAM’S SCAN

The convex hull is a fundamental concept in computational geometry that refers to the smallest convex polygon that contains all the given points in a set. A convex polygon is a polygon where all interior angles are less than 180 degrees, and the convex hull is the smallest such polygon that contains all the points in the set.

The convex hull can be found using a number of algorithms, the most common of which is the Graham scan algorithm. The Graham scan algorithm works by first finding the point with the lowest y-coordinate (or the leftmost point in case of a tie) and using it as the starting point for the convex hull. The algorithm then sorts the remaining points by their polar angle with respect to the starting point, and proceeds to add the points to the convex hull in counterclockwise order. If adding a point creates a concave angle, the previous point is removed from the convex hull.

Graham's scan is an algorithm used to find the convex hull of a set of points in a plane. The convex hull of a set of points is the smallest convex polygon that contains all the points in the set.

The algorithm works by sorting the points based on their polar angle with respect to a reference point. It then uses a stack to keep track of the vertices of the convex hull as it constructs it.

Here is an outline of the steps involved in Graham's scan algorithm:

Find the point with the lowest y-coordinate (or the leftmost point if there are ties) and use it as the reference point.
Sort the remaining points by their polar angle with respect to the reference point.
Initialize an empty stack and push the first two points onto the stack.
For each remaining point, do the following:

Pop the top point from the stack.
If the next point and the current top of the stack make a left turn with the previous point (i.e., the cross product of the vectors formed by the three points is positive), push the next point onto the stack.
Otherwise, repeat step 4 with the same point and the new top of the stack.

When all points have been processed, the stack contains the vertices of the convex hull in counterclockwise order.

Here is an example implementation of Graham's scan algorithm in Java:


public static List<Point> convexHull(Point[] points) {
    int n = points.length;
    if (n < 3) {
        throw new IllegalArgumentException("Convex hull
        requires at least 3 points");
    }

    // Find pivot point with smallest y-coordinate (and smallest
        x-coordinate if tie)
    Point pivot = points[0];
    for (int i = 1; i < n; i++) {
        if (points[i].y < pivot.y || (points[i].y == pivot.y
        && points[i].x < pivot.x)) {
            pivot = points[i];
        }
    }

    // Sort points in increasing order of polar angle with respect to pivot
        point
    Arrays.sort(points, new Comparator<Point>() {
        public int compare(Point p1, Point p2) {
            if (p1 == pivot) {
                return -1;
            } else if (p2 == pivot) {
                return 1;
            } else {
                int orientation =
        orientation(pivot, p1, p2);
                if (orientation == 0)
        {
                    return
        dist(pivot, p1) < dist(pivot, p2) ? -1 : 1;
                } else {
                    return
        orientation < 0 ? -1 : 1;
                }
            }
        }
    });

    // Compute convex hull
    List<Point> hull = new ArrayList<>();
    hull.add(points[0]);
    hull.add(points[1]);
    for (int i = 2; i < n; i++) {
        Point top = hull.remove(hull.size() - 1);
        while (orientation(hull.get(hull.size() - 1), top,
        points[i]) <= 0) {
            top = hull.remove(hull.size() - 1);

        }
        hull.add(top);
        hull.add(points[i]);
    }
    return hull;
}

// Returns the orientation of the three points (p1, p2, p3)
// Returns a positive number if counterclockwise, negative if clockwise, and zero if
        collinear
private static int orientation(Point p1, Point p2, Point p3) {
    return (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y -
        p2.y);
}

// Returns the squared Euclidean distance between two points
private static int dist(Point p1, Point p2) {
    int dx = p1.x - p2.x;
    int dy = p1.y - p2.y;
    return dx *dx + dy * dy;
}

In this implementation, the convexHull method takes an array of Point objects as input and returns a list of points representing the convex hull. The method first finds the pivot point with the smallest y-coordinate (and smallest x-coordinate if tie). It then sorts the remaining points in increasing order of their polar angle with respect to the pivot point. The orientation method is used to compute the orientation of three points and the dist method is used to compute the squared Euclidean distance between two points.

The method then iterates over the sorted points and adds each point to the convex hull if it does not create a right turn. A right turn is created if the last two points on the convex hull and the current point form a clockwise orientation. If a right turn is created, the algorithm removes the last point added to the convex hull and tries again with the new last point.

Graham's scan has a time complexity of O(n log n), where n is the number of points, due to the sorting step. It is widely used in computational geometry and other applications that require the computation of the convex hull of a set of points.

LINE INTERSECTION

Line intersection is a common problem in computational geometry and computer graphics. Given two lines in the plane, the goal is to determine whether they intersect, and if so, to find the point of intersection.

A line in the plane can be represented by the equation:

y = mx + b

where m is the slope of the line, and b is the y-intercept. Alternatively, a line can be represented by two points on the line. Given two lines, we can find their point of intersection by setting the two equations equal to each other and solving for x and y.

If the two lines are parallel, they never intersect and there is no solution. If the two lines are coincident, they overlap and there are infinitely many solutions. Otherwise, there is exactly one solution, which is the point of intersection.

Here is an example implementation of line intersection in Java using the two-point representation:


public static Point lineIntersection(Point p1, Point p2, Point p3, Point p4) {

    int x1 = p1.x, y1 = p1.y;
    int x2 = p2.x, y2 = p2.y;
    int x3 = p3.x, y3 = p3.y;
    int x4 = p4.x, y4 = p4.y;

    int dx1 = x2 - x1;
    int dy1 = y2 - y1;
    int dx2 = x4 - x3;
    int dy2 = y4 - y3;

    int denom = dx1 * dy2 - dy1 * dx2;
    if (denom == 0) {
        // Lines are parallel
        return null;
    }

    int numer1 = x1 * y2 - y1 * x2;
    int numer2 = x3 * y4 - y3 * x4;

    int x = (numer1 * dx2 - dx1 * numer2) / denom;
    int y = (numer1 * dy2 - dy1 * numer2) / denom;

    return new Point(x, y);
}

In this implementation, the lineIntersection method takes four Point objects as input, representing the endpoints of two lines. The method first computes the differences in the x- and y-coordinates of the two lines. It then checks if the lines are parallel by computing the determinant of the system of linear equations. If the determinant is zero, the lines are parallel and there is no solution. Otherwise, it computes the point of intersection using the two-point representation and returns a new Point object representing the intersection point.

Line intersection is a fundamental problem in computational geometry, and is used in many applications, including computer graphics, collision detection, and robotics.

CLOSEST PAIR OF POINTS

The closest pair of points problem is a well-known problem in computational geometry, which involves finding the two points in a set of points that are closest to each other. The problem is often used as a subroutine in other geometric algorithms, such as computing the Voronoi diagram, or in machine learning algorithms, such as clustering.

The brute force solution to this problem is to compute the distance between every pair of points, which takes O(n^2) time. However, there exists a more efficient algorithm that can solve the problem in O(n log n) time.

The algorithm works as follows:

Sort the points by their x-coordinate.
Divide the set of points into two halves.
Recursively find the closest pair of points in each half.
Let d be the minimum of the distances found in the recursive steps.
Consider the strip of points that lie within a distance of d of the middle line, and sort them by their y-coordinate.
For each point p in the strip, compare its distance to the next 7 points in the strip.
Return the pair of points with the smallest distance found in steps 3-6.

The algorithm uses the divide-and-conquer paradigm, where it recursively divides the set of points into two halves and combines the solutions of each half. The key observation is that the closest pair of points must either both lie in the left half, both lie in the right half, or one point lies in the left half and the other lies in the right half.

The strip of points that lie within a distance of d of the middle line is called the "critical strip". By sorting the points in the critical strip by their y-coordinate, we can reduce the number of pairs of points that need to be compared in step 6. It can be shown that we only need to compare each point to the next 7 points in the strip, which can be done in O(n) time.

Here is an example implementation of the closest pair of points algorithm in Java:


public static double closestPair(Point[] points) {
    Arrays.sort(points, Comparator.comparingInt(p -> p.x));
    return closestPairRecursive(points, 0, points.length - 1);
}

private static double closestPairRecursive(Point[] points, int left, int right)
        {
    if (left >= right) {
        return Double.POSITIVE_INFINITY;
    }

    int mid = (left + right) / 2;
    double d1 = closestPairRecursive(points, left, mid);
    double d2 = closestPairRecursive(points, mid + 1, right);
    double d = Math.min(d1, d2);

    List<Point> strip = new ArrayList<>();
    for (int i = left; i <= right; i++) {
        if (Math.abs(points[i].x - points[mid].x) < d)
        {
            strip.add(points[i]);
        }
    }

    Collections.sort(strip, Comparator.comparingInt(p -> p.y));

    for (int i = 0; i < strip.size(); i++) {
        for (int j = i + 1; j < Math.min(i + 8, strip.size());
        j++) {
            if (strip.get(j).y - strip.get(i).y >=
        d) {
                break;
            }
            double dist = dist(strip.get(i),
        strip.get(j));
            d = Math.min(d, dist);
        }
    }

    return d;
}

private static double dist(Point p1, Point p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y -
        p2.y;
    return Math.sqrt(dx * dx + dy * dy);
}

public static void main(String[] args) {
    Point[] points = new Point[5];
    points[0] = new Point(0, 0);
    points[1] = new Point(1, 2);
    points[2] = new Point(2, 3);
    points[3] = new Point(3, 5);
    points[4] = new Point(4, 1);

    double closest = closestPair(points);
    System.out.println("The closest pair of points has distance "
        + closest);
}

In this implementation, the `closestPair` method takes an array of `Point` objects as input and returns the distance between the closest pair of points. The method first sorts the points by their x-coordinate, and then calls the recursive helper method `closestPairRecursive` to compute the closest pair of points. The `closestPairRecursive` method recursively divides the set of points into two halves, and combines the solutions of each half. The method returns the minimum distance found in steps 3-7.

The time complexity of this algorithm is O(n log n), which is dominated by the sorting step. The space complexity is also O(n), which is used to store the critical strip.

The closest pair of points problem is an important problem in computational geometry and has many applications in fields such as machine learning, computer graphics, and robotics.

PROBLEMS

NUMERICAL ALGORITHMS

Easy

Medium

Hard

GEOMETRIC ALGORITHMS