CGAL::monotone_matrix_search

Definition

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 K(n, m) a matrix over K and for 0 i < n:

rmaxM(i) : { min 0 j < m j | M[i, j] = max 0 k < m M[i, k] .}
the (leftmost) column containing the maximum entry in row i. M is called monotone, iff
0 i1 < i2 < n : rmaxM(i1) rmaxM(i2) .
M is totally monotone, iff all of its submatrices are monotone (or equivalently: iff all 2 × 2 submatrices are monotone).

#include <CGAL/monotone_matrix_search.h>

template < class Matrix, class RandomAccessIC, class Compare_strictly >
void
monotone_matrix_search (
Matrix m,
RandomAccessIC t,
Compare_strictly compare_strictly = less< Matrix::Value >())

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 mr of a row r is the leftmost element for which compare_strictly(mr, x) is false for all elements x in r.

Precondition

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

Requirement

  1. Matrix is a model for MonotoneMatrixSearchTraits.
  2. Value type of RandomAccessIC is int.
  3. If compare_strictly is defined, it is an adaptable binary function: Matrix::Value × Matrix::Value bool describing a strict (non-reflexive) total ordering on Matrix::Value.

See Also

MonotoneMatrixSearchTraits
CGAL::all_furthest_neighbors_2
CGAL::maximum_area_inscribed_k_gon_2
CGAL::maximum_perimeter_inscribed_k_gon_2
CGAL::extremal_polygon_2

Implementation

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