Processing math: 100%
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 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...
 

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

rmaxM(i):∈{min0j<mj|M[i,j]=max0k<mM[i,k]}

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

0i1<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).

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 × Matrix::Value 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=(mij)Sr×l (over a totally ordered set S) is sorted, iff

1ir,1j<l:mijmi(j+1)and1i<r,1jl:mijm(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:Sboolwithf(r)tS,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.

Precondition
  1. All matrices in [f,l) are sorted according to Traits::compare_non_strictly.
  2. There is at least one entry x in a matrix M[f,l) 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 O(nk+flog(nk)), 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.