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
- 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 ×
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.
