Applications of the Matrix Maximum

Monotone matrix

A m×n-matrix A = (aij) is called monotone, if for each 1≤i < jm and 1 ≤ k < ln: (aik < ail --> ajk < ajl).

Maximum in a monotone matrix

Problem: Find the maximum in a monotone matrix A = (aij) in linear time (in time O(max{m, n})

We take just the even rows and do:

Step 1:

Step 2:
Now we have a × -matrix A1. We also take just the even rows of A1 and repeat steps 1. We then get A2...

Finally we get a 1×1 matrix Ak. The element aijof it is the row-maximum of the matrix Ak-1. The maximum of first row in Ak-1 must be before aij inclusive. Compare the elements ast in the first row with tj. So we have the maximums of each row in Ak-1 and position all of the maximums in the last matrix Ak-2 to find the maximums of other rows. Last there are m row-maximums in each row. By comparing the m maximums we get the maximum of all elements in the matrix A.

There are O(n) comparisons in total, because the maximum of every odd row will just be between the maximum of the last and the next row, which we already found.

Diameter of a convex polygon

The Diameter of a convex polygon is the maximum of the shortest path inside the polygon from a vertex to another vertex.

Problem: Find the diameter of a given convex polygon P.

Let the vertices of P be numbered clockwise: v1, v2, ..., vn, and denote d(i,j) the length of the shortest path from vi to vj.

This is true for each vertex vi, vj, vl, vm, for all 1 ≤ i < j < l < mn:

d(i,m) + d(j, l)d(i,l) + d(j, m)

then: d(i,l) < d(i,m) --> d(j,l) < d(j,m).

Now we can define the matrix A = (aij), 1≤ in, 1 ≤ jn as follows:

aij = l – n, if 1 ≤ j ≤ i and aij = d(i,j), if i+ 1 ≤ jn.

The matrix A must be a monotone matrix then. We can find the maximum of A in O(n) time.

K-gon of a convex polygon

Problem: Find a convex polygon with k of the n vertices of the convex polygon P = (p1, p2, ..., pn, pn+1 = p1), that the perimeter of the k-gon (polygon with k vertexes) is maximal.

Interleave:Let Q = (q1, q2, ..., qm , qm+1 = q1) and R = (r1, r2, ..., rl, ri>l+1 = r1) be inscribed polygons of P, where as usual the vertices of Q and R are given in clockwise order. If m = l we say that Q and R interleave, if for each 1 ≤ im, vertex r1 is on the polygonal chain of P going clockwise from qi to qi+1, inclusive. If l = m + 1 then Q and R interleave, if q1 = r1 and for 1 ≤ il, vertex ri+1 is on the polygonal chain of P going clockwise from qi to qi+1, inclusive.

Step 1:

We Compute the maximum k-gon at the point p1 as follows:
Compute the maximum 2-gon of P at the point p1, i.e. the longest diagonal of P at the point p1.
Suppose (i–1)-gon Qi-1 = (q1, q2, ..., qi-1) was computed. We find the i-gon based i–1-gon:

Define P(i,j), i = 3,4,...,k and j=1,2,...,m the polygonal chain of P.

P(i,j) = (ps = qj, ps+1, ...,p s+n(i,j) = qj+1)

n(i,j) = the number of vertexes of P(i,j)

and n(i,j)×n(i,j+1)-matrixes A(i,j) = acd(i,j), where acd(i,j) equals the sum of the length from the cth vertex in P(i,j+1) to p1 and length of the longest interleaving-path from p_1 to the cth vertex in P(i,j+1), that passes through the dth vertex in P(i,j).

For example: P = (p1, p2, ..., p6). Suppose the maximal 3-gon at vertex p1 Q = (q1 = p1, q2 = p3, q3 = p4) was computed. Then P(i,j) are P(4,1) = (p1, p2, p3), P(4,2) = (p3, p4), P(4,3) = (p4, p5, p6, p1), n(i,j) are n(4,1) = 3, n(4,2) = 2, n(4,3) = 4, and A(i,j) are A(4,1) A(4,2) A(4,3).

d(x1,...,xn) be the length of the polygonal chain x1,...xn. Bold-typed elements show the row-maximum.

a11(4,2) = maximum of the first row without return to p1 (d(p1, p2, p3) )+ d(p3, p4, p1).

a12(4,2) = maximum of the second row without return to p1 (d(p1, p3, p4) )+ d( p4, p1).

...

The matrices A(i,j) are monotone. So we can use the method above to find the row-maximums. The maximum of the row-maximums be the maximum k-gon of P at the vertex p1.

The time per iteration is O(n) and the total time for the first phase to O(kn).

Based on the k-gon at the vertex p1 we can easily compute the global k-gon of P.

Step 2:

Let Q be the maximum inscribed k-gon rooted at p1 that is returned by the first phase. Choose x to be the middle vertex of the polygonal chain between q1 and q2, and find the maximum k-gon rooted at x, that interleaves with Q. Call this polygon R. The global maximum k-gon must interleave with both Q and R. Let x1 and x2 be the midpoints of the polygonal chains from q1 to x and from x to q2, respectively. The maximum k-gons rooted at x1 and x2 that interleave with Q and R can now both be found in the same amount of time that it took to find R alone. We can continue to divide the intervals in half in this way for a total cost of log n. The second phase uses O(n log n) time.

Literatur:

[1]:J. Hershberger, S. Suri. Matrix Searching with the Shortest Path Metric
[2]:A. Aggarwal, M. Klawe, S. Moran, P. Shor, R. Wilber, Geometric Applications of a Matrix-Searching Algorithm
[3]:Rolf Klein, Elmar Langetepe, Tom Kamphans. Offline-Bewegungsplanung