Sumo de Minkowski
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
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 = 2C
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
redaktiEstas ankaŭ nocio de la esenca sumo de Minkowski +e de du aroj en eŭklida spaco. La esenca sumo de Minkowski estas difinita kiel
kie μ estas n-dimensia lebega mezuro. La kaŭzo por la termino "esenca" estas jena propraĵo de nadlaj funkcioj: se
do
kie ess sup estas la esenca preciza supra rando.
Aplikoj
redaktiPlanado de movo
redaktiSumo 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
redaktiEn 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
redaktiEbena okazo
redaktiDu konveksaj plurlateroj en la ebeno
redaktiPor 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
redaktiSe 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ŭ
redaktiReferencoj
redakti- 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), p. 355–405 (elektroniko).