What is the convex hull?

The convex hull of a set of points in a Euclidean space is the smallest convex shape (polytope) that encloses all the points. Intuitively, you can think of it as the “rubber band” that tightly wraps around the outermost points. After stretching the rubber band around the points, if you let it go, it will form the convex hull.

Key Concepts:

1. Convex: A shape is convex if, for any two points inside the shape, the straight line segment joining them also lies entirely inside the shape. This means there are no “dips” or “indentations” in the shape.
2. Hull: The hull refers to the outer boundary of a set of points, which in the case of a convex hull, is the smallest convex boundary that contains all the points.

Visualization:

Imagine you have a set of points scattered on a flat surface. If you were to take a rubber band, stretch it around the outermost points, and then release it, the rubber band would form the convex hull. This convex boundary would contain all the points inside it.

For example:

• In 2D: The convex hull might form a polygon with straight sides connecting the outermost points.
• In 3D: The convex hull could be a polyhedron with flat faces.

Applications of Convex Hull:

• Geometric problems: It is often used in computational geometry for problems like collision detection or shape recognition.
• Pattern recognition and classification: Convex hulls can be used to identify regions where data points lie. If the convex hulls of two classes (e.g., in classification problems) do not overlap, the classes can be separated by a hyperplane (linear separability).
• Image processing: Convex hulls can be used to simplify shapes in images, representing them by their outermost boundary.

Algorithms for Finding the Convex Hull:

Several algorithms exist to find the convex hull of a set of points, with some popular ones being:

• Graham’s Scan: A well-known and efficient algorithm with a time complexity of O(n log n).
• QuickHull: A divide-and-conquer algorithm with a time complexity of O(n log n) on average.
• Chan’s Algorithm: An optimal algorithm that combines Graham’s scan and other techniques.

Example of Convex Hull in 2D:

Let’s consider a set of points in a 2D plane:
(1, 1), (2, 3), (3, 1), (4, 2), (2, 2), and (3, 3).

The convex hull would be the polygon that connects the outermost points. In this case, it might form a polygon with vertices at (1, 1), (2, 3), (4, 2), and (3, 1).

Convex Hull in Python using SciPy:

Here’s how you can compute and visualize the convex hull of a set of points using SciPy in Python.

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import ConvexHull

# Define some 2D points
points = np.array([[1, 1], [2, 3], [3, 1], [4, 2], [2, 2], [3, 3]])

# Compute the convex hull
hull = ConvexHull(points)

# Plot the points
plt.scatter(points[:, 0], points[:, 1], color='red')

# Plot the convex hull
for simplex in hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], 'b-')

plt.xlabel('X')
plt.ylabel('Y')
plt.title('Convex Hull of Points')
plt.show()

Explanation:

• The ConvexHull function from scipy.spatial computes the convex hull of the given points.
• The simplices attribute of the result provides the edges that form the convex hull.

Example Output:

The plot will show the set of points and the convex hull drawn as a polygon surrounding the outermost points.

---

Summary:

The convex hull is a fundamental concept in computational geometry that provides the smallest convex boundary that contains all the given points. It is widely used in various fields like pattern recognition, computational geometry, and classification tasks. The concept is particularly useful for determining linear separability in classification problems, as two classes of points are linearly separable if their convex hulls do not overlap.

Preceding question:

• How do you determine if two classes are linearly separable in practice?