Sumo de Minkowski

eta|Sumo de Minkowski *A* + *B*
eta|*B*
eta|*A*
En geometrio, la **sumo de Minkowski** aŭ **pligrandiĝo** de du aroj *A* kaj *B* en eŭklida spaco estas la aro de ĉiuj rezultoj de adicio de elemento de *A* al elemento de *B*, kio estas la aro

: A + B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}.

Ekzemple, se
:*A* = { (1, 0), (0, 1), (0, −1)}
kaj
:*B* = { (0, 0), (1, 1), (1, −1)},
do la Sumo de Minkowski estas
:*A* + *B* = { (1, 0), (2, 1), (2, −1), (0, 1), (1, 2), (1, 0), (0, −1), (1, 0), (1, −2)}, kiu aspektas simile al seslatero, kun trifoje ripetita punkto (1,0).

Ĉi tiu operacio estas uzata en teoremo de Minkowski:
:*C* + *C* = 2*C*
por konveksa simetria aro enhavanta nulon, kie en la maldekstra flanko estas la sumo de Minkowski kaj en la dekstra flanko estas la homotetio per faktoro 2.

## Esenca sumo de Minkowski 
Estas ankaŭ nocio de la **esenca sumo de Minkowski** +e de du aroj en eŭklida spaco. La esenca sumo de Minkowski estas difinita kiel

:A +_{\mathrm{e}} B = \{ z \in \mathbb{R}^{n} | \mu (X \cap (z - Y)) > 0 \},

kie *μ* estas *n*-dimensia lebega mezuro. La kaŭzo por la termino "esenca" estas jena propraĵo de nadlaj funkcioj: se

:1_{A + B} (z) = \sup_{x \in \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x),

do

:1_{A +_{\mathrm{e}} B} (z) = \mathop{\mathrm{ess\,sup}}_{x \in \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x),

kie *ess sup* estas la esenca preciza supra rando.

## Aplikoj 
### Planado de movo 
Sumo de Minkowski estas uzitaj en planado de movo de objekto inter obstakloj. Ĝi estas uzata por la kalkulado de la konfigura spaco, kiu estas la aro de ĉiuj konsenteblaj pozicioj de la objekto. En la simpla modelo de paralela movo de objekto en la ebeno, kie la pozicio de objekto povas esti unike precizigita per la pozicio de fiksa punkto de ĉi tiu objekto, la konfigura spaco estas la sumo de Minkowski de la aro de obstakloj kaj la movata objekto.

### Prilaboro de materialoj 
En aŭtomata prilaboro de materialo, la programado de la laborilo uzas tion ke la sumo de Minkowski de la tranĉanta peco kun ĝia trajektorio donas la formo de la eltranĉaĵo de la materialo.

## Algoritmoj por komputo de sumo de Minkowski 
### Ebena okazo 
#### Du konveksaj plurlateroj en la ebeno 
Por du konveksaj plurlateroj *P* kaj *Q* en la ebeno kun *m* kaj *n* verticoj, ilia sumo de Minkowski estas konveksa plurlatero kun *m+n* verticoj kaj povas esti komputita en tempo *O(m+n)* per tre simpla proceduro, kiu povas esti neformale priskribita kiel sekvas. Estu la lateroj de la plurlateroj donitaj en unu direkto, ekzemple, kontraŭhorloĝnadla, laŭ la plurlatera rando. Tiam ĉi tiuj lateroj estas ordigita laŭ la polusa angulo. Oni uzu kunfandan algoritmon je la direktaj eĝoj de *P* kaj *Q* en solan ordigitan vicon *S*. Imagu ke ĉi tiuj lateroj estas solidaj sagoj kiuj povas esti movataj libere konservante ilin paralelo al la iliaj originalaj direktoj. Oni munti ĉi tiujn sagoj en la ordo de la vico *S* per alfiksanta la vosto de la venonta sago al la kapo de la antaŭa sago. La rezultanta plurlatera ĉeno estas konveksa plurlatero kiu estas la sumo de Minkowski de *P* kaj *Q*.

#### Aliaj okazoj 
Se unu plurlatero estas konveksa kaj alia ne estas konveksa, la komplikeco de ilia sumo de Minkowski estas *O(nm)*. Se ili ambaŭ estas nekonveksaj, komplikeco de ilia sumo de Minkowski estas *O((mn)2)*

## Vidu ankaŭ 
* Intervala aritmetiko
* Zonohiperpluredro
* Paralela kurbo
* Erozio

## Referencoj 
* 

Kategorio:Konveksa geometrio
Kategorio:Eŭklida geometrio
Kategorio:Dulokaj operacioj
Kategorio:Geometriaj algoritmoj