Brute Force Algorithms in Computational Geometry: Closest Pair and Convex Hull

Introduction

In this lecture, we apply the Brute Force (BF) design technique to geometric problems. Two major case studies are discussed:

1. Closest Pair of Points – finding the two points that are nearest in a 2D plane.

2. Convex Hull – finding the smallest convex polygon that encloses all points.

These problems appear in air-traffic control, pattern recognition, GIS mapping, image analysis, and bioinformatics.

 Table of Contents

1. Overview of Brute Force in Geometry

2. Problem 1: Closest Pair of Points

   • Problem Statement

   • Brute Force Algorithm

   • Example and Explanation

   • Applications

3. Problem 2: Convex Hull Problem

   • Definition and Key Concepts

   • Brute Force Convex Hull Algorithm

   • Applications of Convex Hull

   • Complexity Comparison

4. Conclusion

Overview of Brute Force in Geometry

The Brute Force approach tests all possible combinations to find an optimal geometric result.
While it’s conceptually simple and widely applicable, its time complexity is high (O(n²)–O(n³)).

Despite inefficiency, brute force helps in:

• Understanding geometric relationships.

• Validating optimized algorithms (e.g., Divide & Conquer, Graham Scan).

• Handling small or pre-sorted datasets effectively.

Problem 1: Closest Pair of Points

Problem Statement

Given a set of n points in 2D space, find the two points that are closest to each other in terms of Euclidean distance.

$$\text{distance}(p_i, p_j) = \sqrt{(x_i – x_j)^2 + (y_i – y_j)^2}$$

distance(pi​,pj​)=(xi​−xj​)2+(yi​−yj​)2​

Brute Force Algorithm

Time Complexity: O(n²)
Space Complexity: O(1)

Example and Explanation

Consider points:
P = {(2, 3), (4, 1), (5, 4), (1, 2)}

Compute distance between all pairs:

Closest pair = (2,3) & (1,2), distance = 1.41

Applications

• Air-Traffic Control: Find two closest aircraft in space.

• Cluster Analysis: Identify similar data points for grouping.

• Face Recognition: Measure Euclidean distance between facial feature vectors.

• Bioinformatics: Compare DNA sequences by similarity metrics.

Problem 2: Convex Hull Problem

Definition and Key Concepts

Definition:
Given a set Q of n points in 2D, find the smallest convex polygon P that encloses all points.

• Convex Set: For any two points p, q ∈ S, the entire line segment pq lies in S.

• Convex Polygon: A polygon where all interior angles < 180°.

• Extreme Points: Points that lie on the outer boundary of the set (cannot be expressed as combinations of others).

Brute Force Convex Hull Algorithm

Idea:
A line segment joining two points (pi, pj) is part of the convex hull if and only if all other points lie on the same side of that line.

Where

$$a = y_2 – y_1,\quad b = x_1 – x_2,\quad c = x_1y_2 – y_1x_2$$

a=y2​−y1​,b=x1​−x2​,c=x1​y2​−y1​x2​

Time Complexity: O(n³)
Space Complexity: O(1)

Applications of Convex Hull

Complexity Comparison

Conclusion

The Brute Force technique offers a direct but computationally expensive way to solve geometric problems like Closest Pair and Convex Hull.
Although these algorithms are not efficient for large data, they help in conceptual understanding and validation of optimized solutions. Here is complete lecture Lecture # 15_new