Définition Fondamentale

La somme de Minkowski de deux ensembles de points \(A\) et \(B\) dans un espace vectoriel est définie par l'ensemble :

Propriétés des Enveloppes Convexes

Pour deux enveloppes convexes \(P\) et \(Q\), les propriétés suivantes simplifient considérablement le calcul :

• La somme de Minkowski \(P + Q\) est elle-même une enveloppe convexe.
• Les arêtes de \(P + Q\) sont composées de l'union des arêtes de \(P\) et de \(Q\).
• Si l'on trie les arêtes des deux polygones par angle polaire, la frontière de la somme est obtenue en mettant bout à bout ces arêtes triées.

Implémentation Algorithmique

Puisque les sommets d'une enveloppe convexe sont déjà ordonnés, nous pouvons utiliser une approche de type fusion (merge) pour combiner les arêtes en temps linéaire \(O(n+m)\).

struct Point {
    long long x, y;
    Point operator+(const Point& p) const { return {x + p.x, y + p.y}; }
    Point operator-(const Point& p) const { return {x - p.x, y - p.y}; }
    long long operator*(const Point& p) const { return x * p.y - y * p.x; }
};

vector<Point> calculerMinkowski(vector<Point>& P, vector<Point>& Q) {
    int n = P.size(), m = Q.size();
    vector<Point> e1(n), e2(m), res;
    
    for(int i = 0; i < n; i++) e1[i] = P[(i + 1) % n] - P[i];
    for(int i = 0; i < m; i++) e2[i] = Q[(i + 1) % m] - Q[i];
    
    res.push_back(P[0] + Q[0]);
    int i = 0, j = 0;
    while(i < n || j < m) {
        if(i < n && (j == m || e1[i] * e2[j] >= 0)) {
            res.push_back(res.back() + e1[i++]);
        } else {
            res.push_back(res.back() + e2[j++]);
        }
    }
    if(res.size() > 1) res.pop_back();
    return res;
}

Applications Classiques

I. Intersection de polygones par translation

Considérons deux ensembles de points dont les enveloppes convexes sont \(A\) et \(B\). On se demande si une translation de \(B\) par un vecteur \(v\) intersecte \(A\). L'intersection existe s'il existe \(a \in A\) et \(b \in B\) tels que \(a = b + v\), ce qui équivaut à \(v = a - b\). En définissant \(-B = \{-b \mid b \in B\}\), le problème revient à vérifier si le point \(v\) appartient à l'enveloppe convexe \(A + (-B)\).

Pour vérifier si un point est à l'intérieur d'une enveloppe convexe de \(N\) points en \(O(\log N)\), on choisit un point de référence (le plus bas à gauche) et on utilise la recherche binaire sur les angles polaires pour identifier le secteur angulaire où se trouve le point, puis on vérifie sa position par rapport à l'arête correspondante.

bool estDansEnveloppe(const vector<Point>& hull, Point p) {
    int n = hull.size();
    Point ref = hull[0];
    if ((p - ref) * (hull[1] - ref) > 0 || (p - ref) * (hull[n-1] - ref) < 0) return false;
    
    int idx = lower_bound(hull.begin() + 1, hull.end(), p, [&](const Point& a, const Point& b) {
        return (a - ref) * (b - ref) > 0;
    }) - hull.begin();
    
    return (p - hull[idx-1]) * (hull[idx] - hull[idx-1]) >= 0;
}

II. Maximisation du produit vectoriel

Dans certains problèmes, on cherche à maximiser le produit vectoriel entre un vecteur fixe \(OP\) et une somme de vecteurs issus d'un ensemble \(S\). La propriété clé est que le vecteur maximisant ce produit se situera nécessairement sur l'enveloppe convexe de l'ensemble des sommes possibles. Si l'on travaille sur des sous-intervalles, on peut utiliser une approche "Diviser pour Régner" combinée à la somme de Minkowski pour construire l'enveloppe globale en \(O(n \log^2 n)\).

III. Problèmes d'optimisation sur Histogrammes

Lors de la recherche de l'aire maximale de l'union de \(k\) rectangles dans un histogramme, on utilise souvent l'arbre cartésien. Pour \(k=3\), une situation complexe apparaît lorsque deux rectangles ne sont pas ancêtres l'un de l'autre mais partagent un ancêtre commun. L'aire de leur union peut être modélisée comme une recherche sur une enveloppe convexe résultant d'une somme de Minkowski. En combinant les propriétés des segments disjoints dans l'arbre cartésien et la somme de Minkowski, on peut résoudre ce cas de figure efficacement.