computes the maximum (as specified by compare_strictly) entry for each row of m and writes the corresponding column to t, i.e., t[i] is set to the index of the column containing the maximum element in row i. The maximum $m_r$ of a row $r$ is the leftmost element for which compare_strictly $(m_r,\,x)$ is false for all elements $x$ in $r$.

The function monotone_matrix_search() computes the maxima for all rows of a totally monotone matrix.

More precisely, monotony for matrices is defined as follows.

Let $K$ be a totally ordered set, $M \in K^{(n,\, m)}$ a matrix over $K$ and for $0 \le i < n$:

$$rmax_M(i) :\in \left\{ \min_{0 \le j < m} j \: \left|\: M[i,\, j] = \max_{0 \le k < m} M[i,\, k] \right.\right\}$$

the (leftmost) column containing the maximum entry in row $i$. $M$ is called monotone, iff

$$\forall\, 0 \le i_1 < i_2 < n\: :\: rmax_M(i_1) \le rmax_M(i_2)\; .$$

$M$ is totally monotone, iff all of its submatrices are monotone (or equivalently: iff all $2 \times 2$ submatrices are monotone).

Precondition

t points to a structure of size at least m.number_of_rows()

Requires:

Matrix is a model for MonotoneMatrixSearchTraits.

Value type of RandomAccessIC is int.

If compare_strictly is defined, it is an adaptable binary function: Matrix::Value $\times$ Matrix::Value $\rightarrow$ bool describing a strict (non-reflexive) total ordering on Matrix::Value.

See Also

MonotoneMatrixSearchTraits

all_furthest_neighbors_2()

maximum_area_inscribed_k_gon_2()

maximum_perimeter_inscribed_k_gon_2()

extremal_polygon_2()

Implementation

The implementation uses an algorithm by Aggarwal et al.[1]. The runtime is linear in the number of rows and columns of the matrix.

#include <CGAL/monotone_matrix_search.h>

returns the element x in one of the sorted matrices from the range [f, l), for which t.is_feasible(x) is true and t.compare(x, y) is true for all other y values from any matrix for which t.is_feasible(y) is true.

The function sorted_matrix_search() selects the smallest entry in a set of sorted matrices that fulfills a certain feasibility criterion.

More exactly, a matrix $M = (m_{i j}) \in S^{r \times l}$ (over a totally ordered set $S$) is sorted, iff

$$\begin{eqnarray*} \forall \, 1 \le i \le r,\; 1 \le j < l\; :\; m_{i j} \le m_{i (j+1)} \;\; {\it and}\\ \forall \, 1 \le i < r,\; 1 \le j \le l\; :\; m_{i j} \le m_{(i+1) j} \;\;. \end{eqnarray*}$$

Now let $\mathcal{M}$ be a set of $n$ sorted matrices over $S$ and $f$ be a monotone predicate on $S$, i.e.

$$f\: :\: S \longrightarrow\, \textit{bool} \quad{\rm with}\quad f(r) \;\Longrightarrow\; \forall\, t \in S\,,\: t > r \; :\; f(t)\;.$$

If we assume there is any feasible element in one of the matrices in $\mathcal{M}$, there certainly is a smallest such element. This is the one we are searching for.

The feasibility test as well as some other parameters can (and have to) be customized through a traits class.

Precondition

1. All matrices in $\left[f,\, l\right)$ are sorted according to Traits::compare_non_strictly.
2. There is at least one entry $x$ in a matrix $M \in \left[f,\, l\right)$ for which Traits::is_feasible(x) is true.

Requires:

Traits is a model for SortedMatrixSearchTraits.

Value type of RandomAccessIterator is Traits::Matrix.

Implementation

The implementation uses an algorithm by Frederickson and Johnson[2], [3] and runs in $\mathcal{O}(n \cdot k + f \cdot \log (n \cdot k))$, where $n$ is the number of input matrices, $k$ denotes the maximal dimension of any input matrix and $f$ the time needed for one feasibility test.

See Also

SortedMatrixSearchTraits

#include <CGAL/sorted_matrix_search.h>

Examples:

Matrix_search/sorted_matrix_search.cpp.