Monge Checks
(convex/monge/check.hpp)

• View this file on GitHub
• Last update: 2026-07-07 18:38:36+09:00
• Include: #include "convex/monge/check.hpp"

Overview

This header checks the Monge or anti-Monge quadrangle inequality.

An H by W matrix A is Monge when

\[A[i][j] + A[k][l] \le A[i][l] + A[k][j]\]

for every i < k and j < l. It is enough to test adjacent rows and columns, which gives an $O(HW)$ checker.

Anti-Monge reverses the inequality and is useful for row maxima.

Interface

Implicit matrices:

template <class Value>
bool is_monge(int row_count, int column_count, Value value);

template <class Value>
bool is_anti_monge(int row_count, int column_count, Value value);

Explicit rectangular matrices:

template <class T>
bool is_monge(const std::vector<std::vector<T>>& matrix);

template <class T>
bool is_anti_monge(const std::vector<std::vector<T>>& matrix);

Empty matrices and matrices with fewer than two rows or columns satisfy both properties vacuously.

The element type must support addition and comparison. Intermediate sums must fit in the element type.

Complexity

$O(HW)$ time and $O(1)$ additional memory.

Required by

• Convex All (convex/all.hpp)
• Monge All (convex/monge/all.hpp)

Verified with

• verify/convex/monge/monge_algorithms.test.cpp
• verify/convex/monge/monge_dp_optimization.test.cpp

Code

#ifndef M1UNE_CONVEX_MONGE_CHECK_HPP
#define M1UNE_CONVEX_MONGE_CHECK_HPP 1

#include <cassert>
#include <vector>

namespace m1une {
namespace convex {

template <class Value>
bool is_monge(int row_count, int column_count, Value value) {
    assert(row_count >= 0);
    assert(column_count >= 0);
    for (int row = 0; row + 1 < row_count; row++) {
        for (int column = 0; column + 1 < column_count; column++) {
            if (value(row, column) + value(row + 1, column + 1) >
                value(row, column + 1) + value(row + 1, column)) {
                return false;
            }
        }
    }
    return true;
}

template <class Value>
bool is_anti_monge(int row_count, int column_count, Value value) {
    assert(row_count >= 0);
    assert(column_count >= 0);
    for (int row = 0; row + 1 < row_count; row++) {
        for (int column = 0; column + 1 < column_count; column++) {
            if (value(row, column) + value(row + 1, column + 1) <
                value(row, column + 1) + value(row + 1, column)) {
                return false;
            }
        }
    }
    return true;
}

template <class T>
bool is_monge(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return is_monge(row_count, column_count,
                    [&](int row, int column) -> const T& { return matrix[row][column]; });
}

template <class T>
bool is_anti_monge(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return is_anti_monge(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

}  // namespace convex
}  // namespace m1une

#endif  // M1UNE_CONVEX_MONGE_CHECK_HPP

#line 1 "convex/monge/check.hpp"



#include <cassert>
#include <vector>

namespace m1une {
namespace convex {

template <class Value>
bool is_monge(int row_count, int column_count, Value value) {
    assert(row_count >= 0);
    assert(column_count >= 0);
    for (int row = 0; row + 1 < row_count; row++) {
        for (int column = 0; column + 1 < column_count; column++) {
            if (value(row, column) + value(row + 1, column + 1) >
                value(row, column + 1) + value(row + 1, column)) {
                return false;
            }
        }
    }
    return true;
}

template <class Value>
bool is_anti_monge(int row_count, int column_count, Value value) {
    assert(row_count >= 0);
    assert(column_count >= 0);
    for (int row = 0; row + 1 < row_count; row++) {
        for (int column = 0; column + 1 < column_count; column++) {
            if (value(row, column) + value(row + 1, column + 1) <
                value(row, column + 1) + value(row + 1, column)) {
                return false;
            }
        }
    }
    return true;
}

template <class T>
bool is_monge(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return is_monge(row_count, column_count,
                    [&](int row, int column) -> const T& { return matrix[row][column]; });
}

template <class T>
bool is_anti_monge(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return is_anti_monge(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

}  // namespace convex
}  // namespace m1une

Back to top page