CGAL::monotone_matrix_search


begin of advanced section  advanced  begin of advanced section

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, tex2html_wrap_inline11 a matrix over K and for tex2html_wrap_inline13 :

displaymath15

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

displaymath19

M is totally monotone, iff all of its submatrices are monotone (or equivalently: iff all tex2html_wrap_inline21 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.

end of advanced section  advanced  end of advanced section