Definition
The convex hull is the smallest convex polygon or shape that encloses a given set of points in a two-dimensional space. It can be visualized as the outer boundary formed by connecting the outermost points in such a way that there are no indentations or concave sections.
For example, imagine placing a rubber band around a group of points on a piece of paper. The convex hull is the shape formed by stretching the rubber band tightly around the outermost points, enclosing all the points within it. It represents the outermost “hull” or boundary of the points, ensuring that all points are inside or on the edge of the polygon.
Types of Convex Hull
- Jarvis Algorithm (Gift wrapping algorithm)
- Graham Scan
- Quick Hull
- Chan’s Algorithm
1. Jarvis Algorithm (Gift wrapping algorithm)
The Jarvis algorithm, also known as the gift-wrapping algorithm, is a simple and natural algorithm used to find the convex hull of a set of points in a two-dimensional space. It is created independently by Chand & Kapur in 1970 but named after R. A. Jarvis, who developed the algorithm in 1973.
Algorithm of Jarvis Method
- Select the leftmost point in the set of points as the starting point. If there are multiple leftmost points, choose the one with the lowest y-coordinate.
- Initialize an empty convex hull list to store the points that form the convex hull.
- Repeat the following steps until we reach the starting point again:
- Select the current point on the convex hull as the next point in the hull.
- Iterate through all the remaining points and find the point that forms the smallest counterclockwise angle (left most side) with the current point. This point will be the next point in the hull.
- Add the next point to the convex hull list.
- Return the convex hull list.
Â
Source Code for Jarvis Method
// COMPUTER GEEK – compgeek.co.in
// Program to generate the convex hull by jarvis method or Gift wrapping method.
Â
#include <stdio.h>
#include <stdlib.h>
typedef struct {
   int x;
   int y;
} Point;
int orientation(Point p, Point q, Point r) {
   int val = (q.y – p.y) * (r.x – q.x) – (q.x – p.x) * (r.y – q.y);
   if (val == 0)
       return 0; // Collinear
   else if (val > 0)
       return 1; // Clockwise
   else
       return 2; // Counter-clockwise
}
void convexHull(Point points[], int n) {
   if (n < 3)
       return;
   int hull[n];
   int leftmost = 0;
   for (int i = 1; i < n; i++) {
       if (points[i].x < points[leftmost].x)
           leftmost = i;
   }
   int p = leftmost, q;
   int count = 0;
   do {
       hull[count++] = p;
       q = (p + 1) % n;
       for (int i = 0; i < n; i++) {
           if (orientation(points[p], points[i], points[q]) == 2)
               q = i;
       }
       p = q;
   } while (p != leftmost);
   // Print the hull points
   for (int i = 0; i < count; i++) {
       printf(“(%d, %d)\n”, points[hull[i]].x, points[hull[i]].y);
   }
}
int main() {
   Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};
   int n = sizeof(points) / sizeof(points[0]);
   printf(“Convex Hull:\n”);
   convexHull(points, n);
   return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Program to generate the convex hull by jarvis method or Gift wrapping method.
Â
#include <iostream>
using namespace std;
Â
struct Point
{
   int x;
   int y;
};
Â
int orientation(Point p, Point q, Point r) {
   int val = (q.y – p.y) * (r.x – q.x) – (q.x – p.x) * (r.y – q.y);
   if (val == 0)
       return 0; // Collinear
   else if (val > 0)
       return 1; // Clockwise
   else
       return 2; // Counter-clockwise
}
Â
void convexHull(Point points[], int n) {
   if (n < 3)
       return;
   int hull[n];
   int leftmost = 0;
   for (int i = 1; i < n; i++) {
       if (points[i].x < points[leftmost].x)
           leftmost = i;
   }
   int p = leftmost, q;
   int count = 0;
   do {
       hull[count++] = p;
       q = (p + 1) % n;
       for (int i = 0; i < n; i++) {
           if (orientation(points[p], points[i], points[q]) == 2)
               q = i;
       }
       p = q;
   } while (p != leftmost);
   // Print the hull points
   for (int i = 0; i < count; i++) {
       cout << “(” << points[hull[i]].x << “, ” << points[hull[i]].y << “)” << endl;
   }
}
Â
int main() {
   Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};
   int n = sizeof(points) / sizeof(points[0]);
   cout << “Convex Hull:” << endl;
   convexHull(points, n);
   return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Program to generate the convex hull by jarvis method or Gift wrapping method.
Â
class Point
{
   int x, y;
  Â
   Point(int x, int y)
  {
       this.x = x;
       this.y = y;
   }
}
Â
public class ConvexHullJarvis
{
   static int orientation(Point p, Point q, Point r)
  {
       int val = (q.y – p.y) * (r.x – q.x) – (q.x – p.x) * (r.y – q.y);
       if (val == 0)
           return 0; // Collinear
       else if (val > 0)
           return 1; // Clockwise
       else
           return 2; // Counter-clockwise
   }
Â
   static void convexHull(Point[] points, int n)
  {
       if (n < 3)
           return;
Â
       int[] hull = new int[n];
       int leftmost = 0;
Â
       for (int i = 1; i < n; i++)
    {
           if (points[i].x < points[leftmost].x)
               leftmost = i;
       }
Â
       int p = leftmost, q;
       int count = 0;
Â
       do
    {
           hull[count++] = p;
           q = (p + 1) % n;
           for (int i = 0; i < n; i++)
      {
               if (orientation(points[p], points[i], points[q]) == 2)
                   q = i;
           }
           p = q;
       } while (p != leftmost);
Â
       // Print the hull points
       for (int i = 0; i < count; i++) {
           System.out.println(“(” + points[hull[i]].x + “, ” + points[hull[i]].y + “)”);
       }
   }
Â
   public static void main(String[] args)
  {
       Point[] points = {new Point(0, 3), new Point(1, 1), new Point(2, 2), new Point(4, 4), new Point(0, 0),
               new Point(1, 2), new Point(3, 1), new Point(3, 3)};
Â
       int n = points.length;
       System.out.println(“Convex Hull:”);
       convexHull(points, n);
   }
}
# COMPUTER GEEK – compgeek.co.in
# Program to generate the convex hull by jarvis method or Gift wrapping method.
Â
class Point:
   def __init__(self, x, y):
       self.x = x
       self.y = y
Â
def orientation(p, q, r):
   val = (q.y – p.y) * (r.x – q.x) – (q.x – p.x) * (r.y – q.y)
   if val == 0:
       return 0 # Collinear
   elif val > 0:
       return 1 # Clockwise
   else:
       return 2 # Counter-clockwise
Â
def convex_hull(points):
   n = len(points)
   if n < 3:
       return
  Â
   hull = []
   leftmost = 0
   for i in range(1, n):
       if points[i].x < points[leftmost].x:
           leftmost = i
  Â
   p = leftmost
   count = 0
   while True:
       hull.append(p)
       q = (p + 1) % n
       for i in range(n):
           if orientation(points[p], points[i], points[q]) == 2:
               q = i
       p = q
       if p == leftmost:
           break
  Â
   # Print the hull points
   for i in hull:
       print(f”({points[i].x}, {points[i].y})”)
Â
if __name__ == “__main__”:
   points = [Point(0, 3), Point(1, 1), Point(2, 2), Point(4, 4),
             Point(0, 0), Point(1, 2), Point(3, 1), Point(3, 3)]
  Â
   print(“Convex Hull:”)
   convex_hull(points)
2. Graham Scan
The Graham scan algorithm is a popular method for finding the convex hull of a set of points in a two-dimensional space. It was developed by Ronald Graham in 1972 and is known for its efficiency.
Algorithm of Graham scan
- Choose the point with the lowest y-coordinate. If multiple points have the same lowest y-coordinate, select the one with the leftmost x-coordinate. This point will be the starting point of the convex hull.
- Sort the remaining points in counterclockwise order based on their angle with the starting point. This can be achieved by calculating the polar angle of each point with respect to the starting point.
- Create an empty stack to hold the points that form the convex hull.
- Push the starting point and the first point from the sorted list onto the stack.
- Iterate through the sorted list of points:
- While the current point and the next point in the sorted list make a non-left turn or are collinear, pop the top point from the stack.
- Push the current point onto the stack.
- Return the points in the stack, which represent the vertices of the convex hull in counterclockwise order.
Working of Graham Scan
- Choose the lowest y-coordinate. (0,0) and (6,0)
- If multiple coordinates are there, choose the leftmost x-coordinate. This will be our starting point. (0,0)
- Sort the remaining points in counterclockwise order.
(0,0), (6,0), (9,5), (4,4), (7,9), (3,7), (1,6), (-1,6)
- Push the starting point and the first point from the sorted list onto the stack.
- Choose the next point in sorted list (9,5) onto the stack and check if new point (4,4) turns left or right from point (9,5) and (6,0).
(a) If turns right, then (4,4) is in the convex hull
(b) If turns left, then (9,5) is in the convex hull
- Now, (4,4) is current point in the sorted list. Choose next point (7,9) onto the stack and check if new point (7,9) turns left or right from point (4,4) and (9,5).
(a) If turns right, then (7,9) is in the convex hull
(b) If turns left, then (4,4) is in the convex hull
- Now, (7,9) is current point in the sorted list. Choose next point (3,7) in the sorted list onto the stack.
- Choose the next point in sorted list (1,6) onto the stack and check if new point (1,6) turns left or right from point (3,7) and (7,9).
(a) If turns right, then (1,6) is in the convex hull
(b) If turns left, then (3,7) is in the convex hull
- Now, (1,6) is current point in the sorted list. Choose next point (-1,6) onto the stack and check if new point (-1,6) turns left or right from point (1,6) and (3,7).
(a) If turns right, then (-1,6) is in the convex hull
(b) If turns left, then (1,6) is in the convex hull
- There is a problem in three points (-1,6), (3,7) and (7,9). These three points are collinear. So, algorithm says that the middle point (3,7) should be discarded and (-1,6) and (7,9) remains in the stack.
- We have used all the points in the sorted list, so Choose the starting point in (0,0) and check if line between (-1,6) to (0,0) point turns left or right from point (-1,6) and (7,9).
(a) If turns right, then (0,0), (6,0), (9,5) and (7,9) points are in the convex hull.
(b) If turns left, then (0,0), (6,0), (9,5), (-1,6) and (7,9) points are in the convex hull.
Iteration is complete, the hull contains the points of the convex hull in counterclockwise order (0,0), (6,0), (9,5), (-1,6) and (7,9).
The Graham scan algorithm effectively eliminates unnecessary points from the convex hull by checking for left turns. That is why it has a smaller time complexity.
The time complexity of the Graham scan algorithm is O(n log n), where n is the number of points in the input set.
Â
Source Code for Graham Scan
// COMPUTER GEEK – compgeek.co.in
// Program to generate convex hull by Graham Scan Algorithm
Â
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
   int x
   int y;
} Point;
Point p0; // Global variable to store the bottommost leftmost point
// Swap two points
void swap(Point* a, Point* b) {
   Point temp = *a;
   *a = *b;
   *b = temp;
}
// Calculate square of Euclidean distance between two points
int distSquare(Point p1, Point p2) {
   return ((p2.x – p1.x) * (p2.x – p1.x)) + ((p2.y – p1.y) * (p2.y – p1.y));
}
// Find the next to top element in the stack
Point nextToTop(Point* stack, int* top) {
   return stack[*top – 1];
}
// Calculate orientation of three points (p, q, r)
int orientation(Point p, Point q, Point r) {
   int val = ((q.y – p.y) * (r.x – q.x)) – ((q.x – p.x) * (r.y – q.y));
   if (val == 0)
       return 0; // Collinear
   else if (val > 0)
       return 1; // Clockwise
   else
       return 2; // Counter-clockwise
}
// Comparison function for sorting points based on polar angle in anti-clockwise direction
int compare(const void* vp1, const void* vp2) {
   Point* p1 = (Point*)vp1;
   Point* p2 = (Point*)vp2;
   int o = orientation(p0, *p1, *p2);
   if (o == 0)
       return (distSquare(p0, *p2) >= distSquare(p0, *p1)) ? -1 : 1;
   return (o == 2) ? -1 : 1;
}
void convexHull(Point points[], int n) {
   // Find the bottommost leftmost point
   int ymin = points[0].y, min = 0;
   for (int i = 1; i < n; i++) {
       int y = points[i].y;
       if ((y < ymin) || (ymin == y && points[i].x < points[min].x)) {
           ymin = points[i].y;
           min = i;
       }
   }
   // Place the bottommost leftmost point at first position
   swap(&points[0], &points[min]);
   // Sort points in anti-clockwise order based on polar angle
   p0 = points[0];
   qsort(&points[1], n – 1, sizeof(Point), compare);
   // If two or more points have the same angle, remove all but the farthest point
   int m = 1;
   for (int i = 1; i < n; i++) {
       while (i < n – 1 && orientation(p0, points[i], points[i + 1]) == 0)
           i++;
       points[m] = points[i];
       m++;
   }
   if (m < 3)
       return; // Convex hull not possible
   Point hull[m]; // Create an empty stack for storing convex hull points
   int top = 0;
   // Push first three points to the stack
   hull[top++] = points[0];
   hull[top++] = points[1];
   hull[top++] = points[2];
   // Process the remaining points
   for (int i = 3; i < m; i++) {
       // Remove points that make a clockwise turn
       while (top > 1 && orientation(nextToTop(hull, &top), hull[top – 1], points[i]) != 2)
           top–;
       // Push the current point to the stack
       hull[top++] = points[i];
   }
   // Print the convex hull points
   printf(“Convex Hull:\n”);
   for (int i = 0; i < top; i++) {
       printf(“(%d, %d)\n”, hull[i].x, hull[i].y);
   }
}
int main() {
   Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};
   int n = sizeof(points) / sizeof(points[0]);
   printf(“Input Points:\n”);
   for (int i = 0; i < n; i++) {
       printf(“(%d, %d)\n”, points[i].x, points[i].y);
   }
   convexHull(points, n);
   return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Program to generate convex hull by Graham Scan Algorithm
Â
#include <iostream>
#include <algorithm>
Â
using namespace std;
Â
struct Point {
   int x, y;
};
Â
Point p0; // Global variable to store the bottommost leftmost point
Â
// Swap two points
void swap(Point* a, Point* b) {
   Point temp = *a;
   *a = *b;
   *b = temp;
}
Â
// Calculate square of Euclidean distance between two points
int distSquare(Point p1, Point p2) {
   return ((p2.x – p1.x) * (p2.x – p1.x)) + ((p2.y – p1.y) * (p2.y – p1.y));
}
Â
// Find the next to top element in the stack
Point nextToTop(Point* stack, int* top) {
   return stack[*top – 1];
}
Â
// Calculate orientation of three points (p, q, r)
int orientation(Point p, Point q, Point r) {
   int val = ((q.y – p.y) * (r.x – q.x)) – ((q.x – p.x) * (r.y – q.y));
   if (val == 0)
       return 0; // Collinear
   else if (val > 0)
       return 1; // Clockwise
   else
       return 2; // Counter-clockwise
}
Â
// Comparison function for sorting points based on polar angle in anti-clockwise direction
int compare(const void* vp1, const void* vp2) {
   Point* p1 = (Point*)vp1;
   Point* p2 = (Point*)vp2;
   int o = orientation(p0, *p1, *p2);
   if (o == 0)
       return (distSquare(p0, *p2) >= distSquare(p0, *p1)) ? -1 : 1;
   return (o == 2) ? -1 : 1;
}
Â
void convexHull(Point points[], int n) {
   // Find the bottommost leftmost point
   int ymin = points[0].y, min = 0;
   for (int i = 1; i < n; i++) {
       int y = points[i].y;
       if ((y < ymin) || (ymin == y && points[i].x < points[min].x)) {
           ymin = points[i].y;
           min = i;
       }
   }
Â
   // Place the bottommost leftmost point at first position
   swap(&points[0], &points[min]);
Â
   // Sort points in anti-clockwise order based on polar angle
   p0 = points[0];
   qsort(&points[1], n – 1, sizeof(Point), compare);
Â
   // If two or more points have the same angle, remove all but the farthest point
   int m = 1;
   for (int i = 1; i < n; i++) {
       while (i < n – 1 && orientation(p0, points[i], points[i + 1]) == 0)
           i++;
       points[m] = points[i];
       m++;
   }
   if (m < 3)
       return; // Convex hull not possible
Â
   Point hull[m]; // Create an empty stack for storing convex hull points
   int top = 0;
Â
   // Push first three points to the stack
   hull[top++] = points[0];
   hull[top++] = points[1];
   hull[top++] = points[2];
Â
   // Process the remaining points
   for (int i = 3; i < m; i++) {
       // Remove points that make a clockwise turn
       while (top > 1 && orientation(nextToTop(hull, &top), hull[top – 1], points[i]) != 2)
           top–;
       // Push the current point to the stack
       hull[top++] = points[i];
   }
Â
   // Print the convex hull points
   cout << “Convex Hull:\n”;
   for (int i = 0; i < top; i++) {
       cout << “(” << hull[i].x << “, ” << hull[i].y << “)\n”;
   }
}
Â
int main() {
   Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};
   int n = sizeof(points) / sizeof(points[0]);
Â
   cout << “Input Points:\n”;
   for (int i = 0; i < n; i++) {
       cout << “(” << points[i].x << “, ” << points[i].y << “)\n”;
   }
Â
   convexHull(points, n);
Â
   return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Program to generate convex hull by Graham Scan Algorithm
Â
import java.util.Arrays;
Â
class ConvexHullGrahamScan {
Â
   static class Point {
       int x, y;
Â
       Point(int x, int y) {
           this.x = x;
           this.y = y;
       }
   }
Â
   static Point p0; // Global variable to store the bottommost leftmost point
Â
   // Swap two points
   static void swap(Point[] points, int i, int j) {
       Point temp = points[i];
       points[i] = points[j];
       points[j] = temp;
   }
Â
   // Calculate square of Euclidean distance between two points
   static int distSquare(Point p1, Point p2) {
       return ((p2.x – p1.x) * (p2.x – p1.x)) + ((p2.y – p1.y) * (p2.y – p1.y));
   }
Â
   // Find the next to top element in the stack
   static Point nextToTop(Point[] stack, int top) {
       return stack[top – 1];
   }
Â
   // Calculate orientation of three points (p, q, r)
   static int orientation(Point p, Point q, Point r) {
       int val = ((q.y – p.y) * (r.x – q.x)) – ((q.x – p.x) * (r.y – q.y));
       if (val == 0)
           return 0; // Collinear
       else if (val > 0)
           return 1; // Clockwise
       else
           return 2; // Counter-clockwise
   }
Â
   // Comparison function for sorting points based on polar angle in anti-clockwise direction
   static class PointComparator implements java.util.Comparator<Point> {
       @Override
       public int compare(Point p1, Point p2) {
           int o = orientation(p0, p1, p2);
           if (o == 0)
               return (distSquare(p0, p2) >= distSquare(p0, p1)) ? -1 : 1;
           return (o == 2) ? -1 : 1;
       }
   }
Â
   static void convexHull(Point[] points, int n) {
       // Find the bottommost leftmost point
       int ymin = points[0].y, min = 0;
       for (int i = 1; i < n; i++) {
           int y = points[i].y;
           if ((y < ymin) || (ymin == y && points[i].x < points[min].x)) {
               ymin = points[i].y;
               min = i;
           }
       }
Â
       // Place the bottommost leftmost point at first position
       swap(points, 0, min);
Â
       // Sort points in anti-clockwise order based on polar angle
       p0 = points[0];
       Arrays.sort(points, 1, n, new PointComparator());
Â
       // If two or more points have the same angle, remove all but the farthest point
       int m = 1;
       for (int i = 1; i < n; i++) {
           while (i < n – 1 && orientation(p0, points[i], points[i + 1]) == 0)
               i++;
           points[m] = points[i];
           m++;
       }
       if (m < 3)
           return; // Convex hull not possible
Â
       Point[] hull = new Point[m]; // Create an empty stack for storing convex hull points
       int top = 0;
Â
       // Push first three points to the stack
       hull[top++] = points[0];
       hull[top++] = points[1];
       hull[top++] = points[2];
Â
       // Process the remaining points
       for (int i = 3; i < m; i++) {
           // Remove points that make a clockwise turn
           while (top > 1 && orientation(nextToTop(hull, top), hull[top – 1], points[i]) != 2)
               top–;
           // Push the current point to the stack
           hull[top++] = points[i];
       }
Â
       // Print the convex hull points
       System.out.println(“Convex Hull:”);
       for (int i = 0; i < top; i++) {
           System.out.println(“(” + hull[i].x + “, ” + hull[i].y + “)”);
       }
   }
Â
   public static void main(String[] args) {
       Point[] points = {new Point(0, 3), new Point(1, 1), new Point(2, 2), new Point(4, 4),
                         new Point(0, 0), new Point(1, 2), new Point(3, 1), new Point(3, 3)};
       int n = points.length;
Â
       System.out.println(“Input Points:”);
       for (Point point : points) {
           System.out.println(“(” + point.x + “, ” + point.y + “)”);
       }
Â
       convexHull(points, n);
   }
}
# COMPUTER GEEK – compgeek.co.in
# Program to generate convex hull by Graham Scan Algorithm
Â
class Point:
   def __init__(self, x, y):
       self.x = x
       self.y = y
Â
def swap(points, i, j):
   temp = points[i]
   points[i] = points[j]
   points[j] = temp
Â
def dist_square(p1, p2):
   return ((p2.x – p1.x) * (p2.x – p1.x)) + ((p2.y – p1.y) * (p2.y – p1.y))
Â
def orientation(p, q, r):
   val = ((q.y – p.y) * (r.x – q.x)) – ((q.x – p.x) * (r.y – q.y))
   if val == 0:
       return 0 # Collinear
   elif val > 0:
       return 1 # Clockwise
   else:
       return 2 # Counter-clockwise
Â
def convex_hull(points):
   # Find the bottommost leftmost point
   ymin = points[0].y
   min_index = 0
   for i in range(1, len(points)):
       if points[i].y < ymin or (points[i].y == ymin and points[i].x < points[min_index].x):
           ymin = points[i].y
           min_index = i
Â
   # Place the bottommost leftmost point at first position
   swap(points, 0, min_index)
Â
   # Sort points in anti-clockwise order based on polar angle
   p0 = points[0]
   points.sort(key=lambda p: (p.x – p0.x, p.y – p0.y))
Â
   # If two or more points have the same angle, remove all but the farthest point
   m = 1
   for i in range(1, len(points)):
       while (i < len(points) – 1 and orientation(p0, points[i], points[i + 1]) == 0):
           i += 1
       points[m] = points[i]
       m += 1
   if m < 3:
       return [] # Convex hull not possible
Â
   hull = [None] * m # Create an empty list for storing convex hull points
   top = 0
Â
   # Push first three points to the stack
   hull[top] = points[0]
   top += 1
   hull[top] = points[1]
   top += 1
   hull[top] = points[2]
   top += 1
Â
   # Process the remaining points
   for i in range(3, m):
       # Remove points that make a clockwise turn
       while (top > 1 and orientation(hull[top – 2], hull[top – 1], points[i]) != 2):
           top -= 1
       # Push the current point to the stack
       hull[top] = points[i]
       top += 1
Â
   # Print the convex hull points
   print(“Convex Hull:”)
   for i in range(top):
       print(“({}, {})”.format(hull[i].x, hull[i].y))
Â
if __name__ == “__main__”:
   points = [Point(0, 3), Point(1, 1), Point(2, 2), Point(4, 4),
             Point(0, 0), Point(1, 2), Point(3, 1), Point(3, 3)]
Â
   print(“Input Points:”)
   for point in points:
       print(“({}, {})”.format(point.x, point.y))
Â
   convex_hull(points)
- Quick Hull is a recursive algorithm that employs a divide and conquer approach. It starts by finding the leftmost and rightmost points and divides the points into two subsets based on the line connecting these extreme points. It recursively finds the convex hull for each subset and then merges them to obtain the final convex hull. Quick Hull has an average time complexity of O(n log n), but it can reach O(n^2) in the worst case.
- Chan’s algorithm combines the benefits of both Gift Wrapping and Graham’s Scan. It initially applies Gift Wrapping to obtain an initial convex hull and then uses Graham’s Scan with a smaller subset of points to improve the performance. Chan’s algorithm developed by Timothy M Chan has a time complexity of O(n log h), where n is the number of points and h is the number of points on the convex hull.
Applications of Convex Hull
- Computational Geometry
- Image Processing
- Robotics and Path Planning
- Geographic Information Systems (GIS)
- Pattern Recognition
Test Yourself
Q1- Explain the concept of the convex hull and its significance in computational geometry.
The convex hull is the smallest convex polygon that encloses a given set of points in a two-dimensional space.
It plays a crucial role in computational geometry as it helps identify the outermost boundary of a set of points, ensuring that all points are inside or on the edge of the polygon.
The convex hull is widely used in various algorithms and applications, such as collision detection, shape recognition, and path planning.
Q2- Compare and contrast the Jarvis Algorithm and Graham Scan for finding the convex hull of a set of points.
Both the Jarvis Algorithm and Graham Scan are methods for finding the convex hull of a set of points. The main difference lies in their approaches. The Jarvis Algorithm (Gift Wrapping) is simpler to implement and finds the convex hull by repeatedly selecting the next point with the smallest counterclockwise angle with the current point. On the other hand, Graham Scan is more efficient, using a divide-and-conquer approach to find the convex hull by sorting points based on their polar angles and then merging the subsets.
Q3- Discuss the time complexity of the Graham Scan algorithm and its implications on the efficiency of finding the convex hull.
The Graham Scan algorithm has an average time complexity of O(n log n), where n is the number of points in the input set. This time complexity is due to the sorting step, which dominates the overall complexity. The efficient time complexity makes Graham Scan suitable for large datasets, making it a popular choice for finding the convex hull.
Q4- Explain the divide-and-conquer strategy employed in the Quick Hull algorithm to find the convex hull.
The Quick Hull algorithm uses a divide-and-conquer strategy to find the convex hull of a set of points.
It starts by identifying the leftmost and rightmost points and divides the points into two subsets based on the line connecting these extreme points.
It then recursively finds the convex hull for each subset and merges the results to obtain the final convex hull. The algorithm divides the problem into smaller subproblems, making it more efficient for larger datasets.
Q5- Compare the performance of Chan’s Algorithm to the other convex hull algorithms and explain its advantage.
Chan’s Algorithm combines the benefits of Gift Wrapping and Graham Scan algorithms.
It uses Gift Wrapping to obtain an initial convex hull and then applies Graham Scan with a smaller subset of points to further improve efficiency.
Chan’s Algorithm has a time complexity of O(n log h), where h is the number of points on the convex hull. This makes it more efficient than other algorithms, especially when dealing with datasets containing a large number of points on the convex hull.
Q6- Explain the significance of the convex hull in robotics and its applications in path planning.
In robotics, the convex hull is crucial for path planning as it defines the safe and accessible regions of the robot’s workspace.
By identifying the convex hull, a robot can determine the outer boundary of obstacles and plan collision-free paths. Convex hull-based algorithms enable efficient path planning, which is essential for autonomous navigation and robotic tasks.
Q7- How does the convex hull find applications in geographic information systems (GIS)?
In GIS, the convex hull is used to determine the boundaries of geographic regions or sets of points. It helps simplify complex geographic data by identifying the outermost boundary of a collection of points or regions. Convex hull-based algorithms are applied in GIS for tasks such as regional analysis, boundary delineation, and spatial data simplification.
Q8-Â Discuss the role of the convex hull in image processing and pattern recognition applications.
In image processing and pattern recognition, the convex hull plays a vital role in object detection and shape analysis.
By finding the convex hull of objects or regions in images, algorithms can distinguish between different shapes and identify their outer boundaries.
Convex hull-based techniques are used in various applications, such as object recognition, fingerprint analysis, and character recognition.
Q9- The time complexity of the Graham Scan algorithm is:
O(n)
O(n log n)
O(n^2)
O(log n)
Ans – (2)
Explanation –Â The Graham Scan algorithm has an average time complexity of O(n log n), where n is the number of points.
Q10- In the Jarvis Algorithm, the next point in the convex hull is selected based on:
Smallest clockwise angle
Smallest counterclockwise angle
Smallest Euclidean distance
Smallest Manhattan distance
Ans – (2)
Explanation –Â The Jarvis Algorithm selects the next point in the convex hull based on the smallest counterclockwise angle with the current point.
Q11- Chan’s Algorithm is a combination of which two convex hull algorithms?
Jarvis Algorithm and Graham Scan
Quick Hull and Graham Scan
Gift Wrapping and Quick Hull
Gift Wrapping and Graham Scan
Ans – (4)
Explanation – Chan’s Algorithm combines the benefits of Gift Wrapping and Graham Scan algorithms.
Q12- Which algorithm employs sorting based on polar angles to find the convex hull?
Jarvis Algorithm
Graham Scan
Quick Hull
Chan’s Algorithm
Ans – (2)
Explanation –Â Graham Scan algorithm uses sorting based on polar angles to find the convex hull.
