Brute Force Closest Pair and Convex-Hull

Closest-Pair Problem

Euclidean distance d(P_i, P_j) = √[(x_i-x_j)² + (y_i-y_j)²]

Find the minimal distance between a pairs in a set of points

Algorithm BruteForceClosestPoints(P)

// P is list of points

dmin ← ∞

for i ← 1 to n-1 do

for j ← i+1 to n do

d ← sqrt((x_i-x_j)² + (y_i-y_j)²)

if d < dmin then

dmin ← d; index1 ← i; index2 ← j

return index1, index2

Note the algorithm does not have to calculate the square root

Then the basic operation is squaring

C(n) = ∑_i=1^n-1 ∑_j=i+1ⁿ 2 = 2∑_j=i+1ⁿ (n-i) = 2n(n-1)/2 ε Θ(n²)

Convex-Hull Problem

A set of points is convex if for any two points, P and Q, the entire line segment, PQ, is in the set.

Illustrate convex and non-convex sets

Convex-hull of a set of points is the smallest convex polygon containing the set.

Illustrate the rubber-band interpretation of the convex hull

The convex-hull of a set of points is composed of some subset of points in the sets.

How to find this subset? Consider the rubber-band figure. What properties do the line segments share?

The rest of the points of set are all on one side.

Two points (x₁, y₁), (x₂, y₂) make the line ax + by = c

where a = y₂-y₁, b = x₁-x₂, and c = x₁y₂ - y₁x₂

And divides the plane by ax + by - c < 0 and ax + by - c > 0

So we need to only check ax + by - c for the rest of the points

What is the worst case cost of the algorithm? O(n³)

Exhaustive Search

Exhaustive search requires searching all the possible solutions (typically combinatorial objects) for the best solution.

Exhaustive search is simply a brute-force approach to combinatorial problems. (Levitin)

Traveling Salesman Problem

The minimal path through all vertices of a weighted graph, visiting each vertex only once.

The Hamiltonian Circuit is a cycle that passes through all the vertices of the graph exactly once.

So they are the same for an un-weighted graph. How to transform a weighted graph?

We concentrate on the Hamiltonian Circuit. If there does exist a circuit then any point can be the start and end vertices. Once a start vertex is chosen then we only need the order of the remaining n-1 vertices. We could generate all the possible ordering of the vertices and calculate the length of the path.

How many possible combination? (n-1)!

Cost for calculating the path? Θ(n)

So the total cost for finding the shortest path? Θ(n!)

Note that half the paths can be eliminated by the direction, so Θ(n!/2)

Knapsack Problem

Given a n item with weights w₁, w₂, ..., w_n and values v₁, v₂,..., v_n and knapsack of capacity W, find the most valuable (max ∑v_j ) that fit in the knapsack (∑w_j ≤ W).

We could generate all possible subsets of items, check feasibility and then value, choosing the sub-set with the maximal value.

How many subsets of n items? 2ⁿ

Both of the problems are NP-hard, meaning there is no know algorithm that solves the problem in polynomial time.

Assignment Problem

Assign n workers to n jobs. Each worker charges a different rate for each job specified by the cost matrix C[i,j].

Note each worker must be assigned to one and only one job.

The cost matrix specifies the problem instance.

A solution can be specified by an n-tuple that specifies the job assignment for the first, second, etc worker.

Then an exhaustive search would generate all the permutations and search for the minimal cost.

Cost of this algorithm? Θ(n!)

There is a better algorithm called the Hungarian method developed by Kong and Egervary.