# Applications of the Matrix Maximum

### Monotone matrix

A *m*×*n*-matrix *A* = (* a_{ij}*) is called
monotone, if for each 1≤

*i*<

*j*≤

*m*and 1 ≤

*k*<

*l*≤

*n*: (

*<*

*a*_{ik}*-->*

*a*_{il}*<*

*a*_{jk}*).*

*a*_{jl}## Maximum in a monotone matrix

**Problem**: Find the maximum in a monotone matrix *A* = (* a_{ij}*) in linear time (in time

*O*(max{

*m*,

*n*})

We take just the even rows and do:

**Step 1:**

- Compare
and*a*_{21}.*a*_{22} - If
<*a*_{21}, then the maximum is not in the first column, eliminate this column.*a*_{22} - Else, compare
and*a*_{42}.*a*_{43} - If
<*a*_{42}*a*_{43}, then the maximum is not in the second column, eliminate this column and compareand*a*_{21}*a*_{23} - Else, store
≥*a*_{22}and compare*a*_{23}and*a*_{63}...*a*_{64}

**Step 2:**

Now we have
a × -matrix
* A_{1}*. We also take just the even rows of

*and repeat steps 1. We then get*

*A*_{1}*...*

*A*_{2}Finally we get a 1×1 matrix * A_{k}*.
The element

*of it is the row-maximum of the matrix*

*a*_{ij}*. The maximum of first row in*

*A*_{k-1}*must be before*

*A*_{k-1}*inclusive. Compare the elements*

*a*_{ij}*in the first row with*

*a*_{st}*t*≤

*j*. So we have the maximums of each row in

*and position all of the maximums in the last matrix*

*A*_{k-1}*to find the maximums of other rows. Last there are*

*A*_{k-2}*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: *v _{1}*,

*v*, ...,

_{2}*v*, and denote

_{n}*d(i*,

*j)*the length of the shortest path from

*to*

*v*_{i}*.*

*v*_{j}This is true for each vertex * v_{i}*,

*,*

*v*_{j}*,*

*v*_{l}*, for all 1 ≤*

*v*_{m}*i*<

*j*<

*l*<

*m*≤

*n*:

*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* = (* a_{ij}*), 1≤

*i*≤

*n*, 1 ≤

*j*≤

*n*as follows:

*a*_{ij} = *l* n, if 1 ≤
*j ≤ i and a_{ij} =
d(i,j), if i+ 1 ≤ j ≤ n.*

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* = (* p_{1}*,

*, ...,*

*p*_{2}*,*

*p*_{n}*p*

*=*

_{n+1}*), that the perimeter of the*

*p*_{1}*k*-gon (polygon with

*k*vertexes) is maximal.

**Interleave**:Let *Q* = (* q_{1}*,

*, ...,*

*q*_{2}

*q*_{m}*,*=

*q*_{m+1}*q*

_{1}) and

*R*= (

*,*

*r*_{1}*, ...,*

*r*_{2}*,*

*r*_{l}*r*i>

_{l+1}=

*r*

_{1}) 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 ≤

*i*≤

*m*, vertex

*is on the polygonal chain of*

*r*_{1}*P*going clockwise from

*to*

*q*_{i}*q*

_{i+1}, inclusive. If*l = m + 1*then*Q*and*R*interleave, if*=**q*_{1}*and for 1 ≤**r*_{1}*i*≤*l, vertex**is on the polygonal chain of**r*_{i+1}*P*going clockwise from*to**q*_{i}*, inclusive.**q*_{i+1}#### Step 1:

We Compute the maximum *k*-gon at the point * p_{1}* as follows:

Compute the maximum 2-gon of

*P*at the point

*, i.e. the longest diagonal of*

*p*_{1}*P*at the point

*.*

*p*_{1}Suppose (

*i1*)-gon

*= (*

*Q*_{i-1}*,*

*q*_{1}*, ...,*

*q*_{2}*) was computed. We find the*

*q*_{i-1}*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)* = (*p*_{s} =
*q*_{j}*, p_{s+1}*, ...,

*)*

*p*_{s+n(i,j)}=*q*_{j+1}*n(**i,j)* = the number of vertexes
of *P(i,j)*

and *n(i,j)*×*n(i,j+1)*-matrixes *A(i,j)* =
* a_{cd(i,j)}*, where

*a*

_{cd(i,j)}equals the sum of the length from the

*c*th vertex in

*P(i,j+1*) to

*and length of the longest interleaving-path from*

*p*_{1}*p_1*to the

*c*th vertex in

*P(i,j+1*), that passes through the

*d*th vertex in

*P(i,j*).

**For example**: *P* =
(* p_{1}*,

*, ...,*

*p*_{2}*). Suppose the maximal 3-gon at vertex*

*p*_{6}

*p*_{1}*Q*= (

*=*

*q*_{1}*,*

*p*_{1}*=*

*q*_{2}*,*

*p*_{3}*=*

*q*_{3}*) was computed. Then*

*p*_{4}*P(i,j*) are

*P(4,1)*= (

*,*

*p*_{1}*,*

*p*_{2}*),*

*p*_{3}*P(4,2)*= (

*),*

*p*_{3},*p*_{4}*P(4,3)*= (

*,*

*p*_{4}*,*

*p*_{5}*),*

*p*_{6},*p*_{1}*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(** x_{1},...,x_{n})* be the length of the polygonal chain

*,...*

*x*_{1}*x*

_{n}. Bold-typed elements show the row-maximum.

* a_{11(4,2)}* = maximum of the first row without
return to

*(*

*p*_{1}*d(*) )+

*p*_{1},*p*_{2},*p*_{3}*d(*

*p*_{3},*p*_{4},*p*_{1}).* a_{12(4,2)}* = maximum of the second row without
return to

*(*

*p*_{1}*d(*) )+

*p*_{1},*p*_{3},*p*_{4}*d(*

*p*_{4},*p*_{1})....

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 * p_{1}*.

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 * p_{1}* we can easily
compute the global

*k*-gon of

*P*.

#### Step 2:

Let *Q* be the maximum inscribed *k*-gon rooted
at * p_{1}* that is returned by the first
phase. Choose

*x*to be the middle vertex of the polygonal chain between

*and*

*q*_{1}*, and find the maximum*

*q*_{2}*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

*and*

*x*_{1}*be the midpoints of the polygonal chains from*

*x*_{2}*to*

*q*_{1}*x*and from

*x*to

*, respectively. The maximum*

*q*_{2}*k*-gons rooted at

*and*

*x*_{1}*that interleave with*

*x*_{2}*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 |