Chapter 9
Monotone and Sorted Matrix Search

Michael Hoffmann

CGAL::monotone_matrix_search and CGAL::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 modelled 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.