Convex Hull (Brute Force Algorithm)

Previous Topics:

• Convex Hull (Introduction)
• Convex Hull( Geometric Primitives)
• Convex Hull ( Geomatric Primitives-I)
• Convex Hull ( Geomatric Primitives-II)
• Convex Hull ( Geomatric Primitives-III)

Find Convex Hull from a Set of Points (Brute Force Algorithm):

---

There are two variants of the convex hull problem:

[1]. Obtain the vertices of the convex hull ( these vertices are also called extreme points);
[2]. Obtain the vertices of the convex hull in some order (clockwise, for example).

Now a simple algorithm is to be describing to find the extreme points of a given set S of points in the plane. To check whether a particular point p ε S is extreme, look at each possible triplet of points and see whether p lies in the triangle formed by these three points. If p lies in any such triangle, it is not extreme, otherwise it is. If there are n points then there are ⁿC₃ possible triangles.

So it takes Θ(n³) times to determine whether a given point is an extreme point or not. Since there are n points, this algorithm runs in a total of Θ(n⁴) times^{(Naive Brute force)}.

---

Code In C/C++:

---

---

Code in C/C++: (graphically implement , used compiler: TC

---

In the implementation of the problem, for each pair of point’s p1 and p2, a brute force algorithm determines whether all other points lie to the same side of a straight line through p1 and p2. If so, the line segment connecting p1 and p2 is a part of the convex hull’s boundary.

---

Algorithm

---

The time efficiency of this algorithm is Θ(n³) ^{(Better Brute force)}.