CGAL 4.5 - Monotone and Sorted Matrix Search
|
This chapter describes concepts, classes, and functions for monotone and sorted matrix search.
The optimization code uses infix OPTIMISATION
in the assertions, e.g. defining the compiler flag CGAL_OPTIMISATION_NO_PRECONDITIONS
switches precondition checking off, cf. Section Checks in the chapter on STL extensions.
CGAL::monotone_matrix_search
CGAL::Dynamic_matrix<M>
MonotoneMatrixSearchTraits
BasicMatrix
CGAL::sorted_matrix_search
CGAL::Sorted_matrix_search_traits_adaptor<F,M>
SortedMatrixSearchTraits
Modules | |
Concepts | |
Classes | |
class | CGAL::Dynamic_matrix< M > |
The class Dynamic_matrix is an adaptor for an arbitrary matrix class M to provide the dynamic operations needed for monotone matrix search. More... | |
class | CGAL::Sorted_matrix_search_traits_adaptor< F, M > |
The class Sorted_matrix_search_traits_adaptor can be used as an adaptor to create sorted matrix search traits classes for arbitrary feasibility test and matrix classes F resp. M . More... | |
Functions | |
template<class Matrix , class RandomAccessIC , class Compare_strictly > | |
void | CGAL::monotone_matrix_search (const Matrix &m, RandomAccessIC t, const 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. More... | |
template<class RandomAccessIterator , class Traits > | |
Traits::Value | CGAL::sorted_matrix_search (RandomAccessIterator f, RandomAccessIterator l, const Traits &t) |
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. More... | |
void CGAL::monotone_matrix_search | ( | const Matrix & | m, |
RandomAccessIC | t, | ||
const 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.
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):∈{min0≤j<mj|M[i,j]=max0≤k<mM[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).
t
points to a structure of size at least m.number_of_rows()
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
.
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>
Traits::Value CGAL::sorted_matrix_search | ( | RandomAccessIterator | f, |
RandomAccessIterator | l, | ||
const Traits & | t | ||
) |
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=(mij)∈Sr×l (over a totally ordered set S) is sorted, iff
∀1≤i≤r,1≤j<l:mij≤mi(j+1)and∀1≤i<r,1≤j≤l:mij≤m(i+1)j.
Now let M be a set of n sorted matrices over S and f be a monotone predicate on S, i.e.
f:S⟶boolwithf(r)⟹∀t∈S,t>r:f(t).
If we assume there is any feasible element in one of the matrices in 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.
Traits::compare_non_strictly
. Traits::is_feasible(x)
is true. 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 O(n⋅k+f⋅log(n⋅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.
SortedMatrixSearchTraits
#include <CGAL/sorted_matrix_search.h>