FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Convex Hull



Introduction

A Convex Hull is the smallest convex polygon that completely encloses a given set of points in a two-dimensional plane. It can be imagined as stretching a rubber band around a group of nails fixed on a board. When the rubber band is released, it tightly surrounds the outermost points. These outer points form the Convex Hull.

Convex Hull is one of the most important problems in Computational Geometry. Several algorithms such as Graham Scan, Jarvis March and Divide and Conquer Convex Hull are used to solve this problem efficiently.

Why Do We Need Convex Hull?

Convex Hull helps in identifying the outer boundary of a set of points. It is widely used in computer graphics, robotics, image processing, GIS systems and pattern recognition.

Application Purpose
Computer Graphics Generating object boundaries.
Image Processing Object detection and shape analysis.
Robotics Obstacle detection and path planning.
GIS Boundary mapping and geographical analysis.
Pattern Recognition Identifying the outer boundary of data points.

Prerequisites

Concept Description
Point A location in a two-dimensional plane.
Polygon A closed figure formed by joining line segments.
Convex Polygon A polygon in which every interior angle is less than 180°.
Divide and Conquer Breaking a problem into smaller subproblems and combining their solutions.

Working Principle

The Divide and Conquer approach divides the given set of points into two smaller subsets. The Convex Hull of each subset is computed recursively. Finally, both hulls are merged to obtain the Convex Hull of the complete set of points.

Illustration


            ●

      ●            ●

   ●      ●   ●

      ●

 ●               ●


Outer Boundary

● -------- ●

|          |

|          |

● -------- ●

Figure 1 : Convex Hull of a Set of Points

Real-Life Example

Suppose several trees are planted in a garden. If a fence is to be constructed around all the trees using the minimum boundary, the fence will pass only through the outermost trees. This outer boundary is called the Convex Hull.

Example

Point Coordinate
P1 (1,1)
P2 (2,5)
P3 (5,4)
P4 (6,1)
P5 (3,3)

The Convex Hull consists of the outermost points P1, P2, P3 and P4. Point P5 lies inside the boundary and is therefore not part of the Convex Hull.

Convex Hull Algorithm (Divide and Conquer)

ConvexHull(PointSet) Step 1 : Divide the given set of points into two halves. Step 2 : Recursively compute the Convex Hull of the left half. Step 3 : Recursively compute the Convex Hull of the right half. Step 4 : Merge the two Convex Hulls. Step 5 : Remove unnecessary interior points. Step 6 : Display the final Convex Hull.

Complexity Analysis

Operation Time Complexity Remarks
Sorting Points O(n log n) Points are sorted before processing.
Divide and Merge O(n log n) Recursive division and merging of hulls.
Total Time Complexity O(n log n) Efficient for large datasets.
Space Complexity O(n) Additional memory is required during recursion.

Popular Convex Hull Algorithms

Algorithm Time Complexity Description
Jarvis March (Gift Wrapping) O(nh) Efficient when the number of hull points is small.
Graham Scan O(n log n) One of the most commonly used Convex Hull algorithms.
Divide and Conquer O(n log n) Recursively divides and merges point sets.

Advantages of Convex Hull

  • Efficiently determines the outer boundary of a set of points.
  • Useful for solving many Computational Geometry problems.
  • Suitable for handling large point datasets.
  • Provides the minimum convex boundary.
  • Forms the basis of many geometric algorithms.

Limitations of Convex Hull

  • Applicable mainly to geometric datasets.
  • Implementation is comparatively complex.
  • Interior points are ignored.
  • Requires sorting before processing.

Applications of Convex Hull

Application Description
Computer Graphics Object boundary generation.
Image Processing Shape detection and segmentation.
Robotics Obstacle avoidance and path planning.
Geographical Information Systems (GIS) Boundary mapping and spatial analysis.
Pattern Recognition Feature extraction and object classification.
Machine Learning Data clustering and outlier detection.

Graham Scan vs Jarvis March

Graham Scan Jarvis March
Time Complexity: O(n log n) Time Complexity: O(nh)
Uses sorting of points. Selects boundary points one by one.
Suitable for large datasets. Suitable when hull points are few.
More efficient in most practical applications. Simpler but slower for large datasets.

Important Points

  • Convex Hull represents the smallest convex polygon enclosing all given points.
  • The Divide and Conquer approach recursively divides the point set into smaller subsets.
  • The Convex Hulls of the subsets are merged to obtain the final solution.
  • The overall time complexity is O(n log n).
  • Convex Hull is one of the most important problems in Computational Geometry.

Exam Tip

In AKTU examinations, students are commonly asked to define the Convex Hull, explain its real-life applications and write the Divide and Conquer approach used for its construction. They may also ask for the difference between Graham Scan and Jarvis March algorithms.

Summary

A Convex Hull is the smallest convex polygon that encloses all points of a given dataset. The Divide and Conquer approach computes the Convex Hull efficiently by recursively dividing the point set and merging the resulting hulls. Due to its O(n log n) time complexity, it is widely used in Computational Geometry, Computer Graphics, Robotics, GIS and Machine Learning.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com