Introduction

For a finite 2D set of points, the "greatest linear dimension" usually means the maximum distance between any two points in the set. In computational geometry this is called the diameter of the point set, and the right algorithm depends on whether you want a simple answer or the best asymptotic performance.

Brute Force Definition

Given points p1, p2, ... pn, the diameter is the largest Euclidean distance between any pair. The direct formula is the usual distance formula:

distance = sqrt((x2 - x1)^2 + (y2 - y1)^2)

The simplest algorithm checks every pair and keeps the maximum. That works well for small inputs and is easy to implement correctly.

1import math
2
3def diameter_bruteforce(points):
4    best = 0.0
5    pair = None
6    for i in range(len(points)):
7        for j in range(i + 1, len(points)):
8            x1, y1 = points[i]
9            x2, y2 = points[j]
10            d = math.hypot(x2 - x1, y2 - y1)
11            if d > best:
12                best = d
13                pair = (points[i], points[j])
14    return best, pair
15
16pts = [(1, 2), (4, 6), (7, 8)]
17print(diameter_bruteforce(pts))

This is O(n^2), which is fine for modest n.

Why the Convex Hull Matters

If the set is large, you do not need to compare every interior point. The farthest pair must lie on the convex hull. That reduces the problem:

1. compute the convex hull
2. find the farthest pair on the hull

Once the hull is known, rotating calipers can find the diameter in linear time with respect to the hull size. The overall complexity becomes O(n log n) because hull construction dominates.

Practical Example

Suppose the points are (1, 2), (4, 6), and (7, 8). The farthest pair is (1, 2) and (7, 8), whose distance is:

sqrt((7 - 1)^2 + (8 - 2)^2) = sqrt(72)

That value is about 8.49. In this tiny example, brute force is the obvious choice, but the mathematical object being computed is the same diameter you would compute with hull-based methods on large data.

A Performance-Oriented View

For many real datasets, the choice is simple:

• use brute force when n is small or code simplicity matters
• use convex hull plus rotating calipers when n is large

This matters in map processing, clustering prechecks, bounding geometry, and graphics pipelines. The diameter is often used as a measure of spatial extent before more expensive analysis begins.

Numerical Stability and Implementation Notes

If you only need the farthest pair and not the literal distance, compare squared distances instead of calling sqrt each time. That avoids unnecessary floating-point work:

1def sqdist(a, b):
2    dx = a[0] - b[0]
3    dy = a[1] - b[1]
4    return dx * dx + dy * dy

This is a small optimization, but it is standard practice in geometry code.

Common Pitfalls

• Confusing greatest linear dimension with width or bounding-box diagonal.
• Using an O(n^2) scan on very large point sets without considering hull reduction.
• Forgetting that the farthest pair must lie on the convex hull.
• Calling sqrt in every comparison when squared distances would do.
• Ignoring duplicate points or empty-input edge cases.

Summary

• The greatest linear dimension of a 2D point set is usually its diameter.
• Brute force checks every pair and runs in O(n^2).
• For large inputs, the farthest pair lies on the convex hull.
• Convex hull plus rotating calipers gives an O(n log n) overall approach.
• For small datasets, the simple pairwise scan is often the best practical solution.