\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5 - Monotone and Sorted Matrix Search
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Monotone and Sorted Matrix Search Reference

matrix.png
Michael Hoffmann
This package provides a matrix search framework, which is the underlying technique for the computation of all furthest neighbors for the vertices of a convex polygon, maximal k-gons inscribed into a planar point set, and computing rectangular p-centers.


Introduced in: CGAL 1.1
BibTeX: cgal:h-msms-14b
License: GPL

This chapter describes concepts, classes, and functions for monotone and sorted matrix search.

Assertions

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.

Classified Reference Pages

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 \( 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\). 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...
 

Function Documentation

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 \( 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>

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.

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.