CGAL 6.2 - Monotone and Sorted Matrix Search

Loading...
Searching...
No Matches
User Manual

Author
  Michael Hoffmann

`monotone_matrix_search()` and `sorted_matrix_search()` are techniques that deal with the problem of efficiently finding largest entries in matrices with certain structural properties. Many concrete problems can be modeled as matrix search problems, and for some of them we provide explicit solutions that allow you to solve them without knowing about the matrix search technique. Examples are, 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.

# Example

In the following program we build a random vector \( a = (a_i)_{i = 1,\,\ldots,\,5}\) (elements drawn uniformly from \( \{ 0,\,\ldots,\,99 \}\)) and construct a Cartesian matrix \( M\) containing as elements all sums \( a_i + a_j,\: i,\,j \in \{1,\,\ldots,\,5\}\). If \( a\) is sorted, \( M\) is sorted as well. So we can apply `sorted_matrix_search()` to compute the upper bound for the maximal entry of \( a\) in \( M\).

Example: Matrix_search/sorted_matrix_search.cpp

Show / Hide
#include <CGAL/Random.h>
#include <CGAL/Cartesian_matrix.h>
#include <CGAL/sorted_matrix_search.h>
#include <vector>
#include <algorithm>
#include <iterator>
#include <boost/functional.hpp>
typedef int Value;
typedef std::vector<Value> Vector;
typedef Vector::iterator Value_iterator;
typedef std::vector<Vector> Vector_cont;
typedef CGAL::Cartesian_matrix<std::plus<int>,
Value_iterator,
Value_iterator> Matrix;
int main()
{
// set of vectors the matrices are build from:
Vector_cont vectors;
// generate a random vector and sort it:
Vector a;
const int n = 5;
for (int i = 0; i < n; ++i)
a.push_back(CGAL::get_default_random()(100));
std::sort(a.begin(), a.end());
std::cout << "a = ( ";
std::copy(a.begin(), a.end(), std::ostream_iterator<int>(std::cout," "));
std::cout << ")\n";
// build a Cartesian matrix from a:
Matrix M(a.begin(), a.end(), a.begin(), a.end());
// search for an upper bound for max(a):
Value bound = a[n-1];
Value upper_bound =
CGAL::sorted_matrix_search(
&M, &M + 1,
CGAL::sorted_matrix_search_traits_adaptor(
[&bound](const auto& m){ return std::greater_equal<Value>()(m, bound); }, M));
std::cout << "Upper bound for " << bound << " is "
<< upper_bound << "." << std::endl;
return 0;
}
CGAL::sorted_matrix_search
Traits::Value 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....