Euclid’s Algorithm and Convex Hull Computation
Euclid’s Algorithm for Finding the Greatest Common Divisor
Euclid’s algorithm is an efficient method for finding the greatest common divisor (GCD) of two integers. The GCD of two numbers a and b is the largest integer that divides both a and b without leaving a remainder.
Steps of Euclid’s Algorithm
- Base Case: If b=0, then GCD(a,b)=a.
- Recursive Step: If b≠0, replace a with b and b with a mod b (the remainder when a is divided by b).
- Repeat the process until b=0, at which point a is the GCD.
Algorithm
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
Example
Find GCD(48, 18):
- 48 mod 18 = 12, so replace a=18, b=12.
- 18 mod 12 = 6, so replace a=12, b=6.
- 12 mod 6 = 0, so the GCD is 6.
Thus, GCD(48,18)=6.
Proof of Correctness
Euclid’s algorithm is based on the principle that the GCD of two numbers is the same as the GCD of the smaller number and the remainder of the division of the larger number by the smaller one.
Key observation: The remainder when dividing a by b is given by: a=bq+r where r=a mod b and q is the quotient. Since the GCD divides both a and b, it must also divide the remainder r. Thus, the GCD of a and b is the same as the GCD of b and r. This process continues until r=0, at which point the GCD is b, the last non-zero remainder.
Time Complexity Analysis
The time complexity of Euclid’s algorithm depends on the number of recursive steps required, which is proportional to the logarithm of the smaller of the two numbers. Specifically, the number of steps is at most O(log(min(a,b))).
In each step, the size of the numbers reduces approximately by half, as we replace a and b with b and a mod b, respectively.
In the worst case, the algorithm performs O(log(min(a,b))) divisions.
Thus, the time complexity of Euclid’s algorithm is O(log(min(a,b))).
Convex Hull of a Set of Points in a Plane
The convex hull of a set of points in a plane is the smallest convex polygon that can enclose all the points in the set. Imagine a rubber band stretched around the outermost points, and when released, it forms the convex hull.
- Convex: A polygon is convex if, for any two points inside the polygon, the line segment connecting them is entirely inside the polygon.
- Hull: The convex hull is essentially the boundary that encloses all the points.
The convex hull is important in computational geometry and has applications in areas such as pattern recognition, image processing, and game development.
Efficient Algorithm: Graham’s Scan
One of the most efficient algorithms for computing the convex hull is Graham’s Scan. This algorithm works by sorting the points and then processing them in a specific order to identify the convex hull.
Steps of Graham’s Scan
- Find the Lowest Point: Select the point with the lowest y-coordinate (if there are multiple points with the same y-coordinate, select the one with the smallest x-coordinate). This point will serve as the pivot or anchor point.
- Sort Points by Polar Angle: Sort the remaining points based on the polar angle they make with the pivot. The polar angle is calculated relative to the pivot point. In the case of a tie (same angle), choose the closest points first.
- Construct the Hull:
- Start with the pivot point and the first two sorted points.
- For each subsequent point, check if moving to that point would form a left turn or a right turn.
- Left turn: Continue adding the point to the hull.
- Right turn: Remove the last point from the hull, as it cannot be part of the convex hull.
- Repeat this process for all points.
- End Condition: When all points have been processed, the points remaining in the hull form the convex hull.
import math
def graham_scan(points):
# Step 1: Find the pivot (point with lowest y-coordinate)
pivot = min(points, key=lambda p: (p[1], p[0]))
# Step 2: Sort points by polar angle with respect to the pivot
points.sort(key=lambda p: (math.atan2(p[1] - pivot[1], p[0] - pivot[0]), p))
# Step 3: Construct the convex hull using a stack
hull = []
for point in points:
while len(hull) >= 2 and cross_product(hull[-2], hull[-1], point) <= 0:
hull.pop() # Remove the last point if it's a right turn
hull.append(point)
return hull
def cross_product(p1, p2, p3):
# Calculate the cross product of vector (p1p2) and (p2p3)
return (p2[0] - p1[0]) * (p3[1] - p2[1]) - (p2[1] - p1[1]) * (p3[0] - p2[0])
Time Complexity Analysis
- Finding the Pivot: This step takes O(n) time, where n is the number of points, as it involves scanning through the list once.
- Sorting the Points: Sorting the points based on the polar angle takes O(n log n) time.
- Constructing the Hull: The process of constructing the convex hull (iterating through the sorted points and using the stack) takes O(n) time.