Convex Hull

The convex-hull problem entails finding the convex-hull of a given set of points.A convex hull is the smallest convex polygon that encloses all the points in the set.

Example Outputs

Test Case 1:

KirkPatrick-Seidel:

Input: (0,2) (4,4) (4,0) (6,2) (2,4) (2,0)

Output: (0,2) (2,4) (4,4) (6,2) (4,0) (2,0)

Jarvis March:

Input: (0,2) (4,4) (4,0) (6,2) (2,4) (2,0)

Output: (4,0) (6,2) (4,4) (2,4) (0,2) (2,0)

Test Case 2:

KirkPatrick-Seidel:

Input: (0,2) (4,4) (4,0) (6,2) (2,4) (2,0) (3,3) (4,0) (5,5) (1,1)

Output: (0,2) (2,4) (5,5) (6,2) (4,0) (2,0)

Jarvis March:

Input: (0,2) (4,4) (4,0) (6,2) (2,4) (2,0) (3,3) (4,0) (5,5) (1,1)

Output: (4,0) (6,2) (5,5) (2,4) (0,2) (1,1) (2,0)

Test Case 3:

KirkPatrick-Seidel:

Input: (2,1) (4,3) (6,5) (1,3) (3,1) (5,4) (0,2) (2,4) (4,0) (6,2)

Output: (0,2) (2,4) (6,5) (6,2) (4,0)

Jarvis March:

Input: (2,1) (4,3) (6,5) (1,3) (3,1) (5,4) (0,2) (2,4) (4,0) (6,2)

Output: (4,0) (6,2) (6,5) (2,4) (0,2)

Tasks

KirkPatrick-Seidel Algorithm

Build the convex hull for a set of points using KirkPatrick-Seidel algorithm.

Jarvis March Algorithm

Build the convex hull for a set of points using Jarvis March algorithm.

Comparison

Compare the complexities of the two algorithms.

Members

A coordinated effort by G2:
      2021A7PS0050H (Siddhant Srinivas)
      2021A7PS1345H (Bhaskar Ruthvik Bikkina)
      2021A7PS0427H (Nikhil Mallu Dhanaraj)
      2021A7PS0379H (B.Sricharan Reddy)
      2021A7PS1502H (Pritam Reddy Nandikonda)