Sumo de Minkowski

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
Sumo de Minkowski A + B
B
A

En geometrio, la sumo de Minkowskipligrandiĝo de du aroj A kaj B en eŭklida spaco estas la aro de ĉiuj rezultoj de adicio ero de A al ero de B, kio estas la aro

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

Aŭ ĝi povas esti skribita kiel

A + B = \{ z \in \mathbb{R}^{n} | X \cap (z - Y) \neq \emptyset \}.

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 tri ripetitaj punktoj je (1,0).

Ĉi tiu operacio estas uzata en teoremo de Minkowski:

C + C = 2C

por konveksa simetria aro enhavanta na 0, 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[redakti | redakti fonton]

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[redakti | redakti fonton]

Planado de movo[redakti | redakti fonton]

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[redakti | redakti fonton]

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[redakti | redakti fonton]

Ebena okazo[redakti | redakti fonton]

Du konveksaj plurlateroj en la ebeno[redakti | redakti fonton]

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[redakti | redakti fonton]

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ŭ[redakti | redakti fonton]

Referencoj[redakti | redakti fonton]

"{{{titolo}}}", gazeto : {{{gazeto}}} Gardner, Richard J. (2002). "The Brunn-Minkowski inequality - La neegalaĵo de Brunn-Minkowski". Bulletin of the American Mathematical Society (N.S.) - Bulteno de la Amerika Matematika Socio 39 (3): 355–405 (elektroniko)