Narodil se 22. 6. 1864. Studoval na univerzitách v Berlíně a Königsbergu. Učil na univerzitách v Bonnu, Königsbergu and Zurichu. V Zurichu byl jeho studentem A. Einstein. V roce 1907 Minkowski pochopil, že práce Lorentze and Einsteina budou lépe pochopitelné v neeuklidovském prostoru. Jeho hlavní práce v tomto oboru jsou Raum und Zeit (1907) and Zwei Abhandlungen über die Grundgleichungen der Elektrodynamik (1909). Minkowski se zabýval hlavně čistou matematikou a věnoval mnoho času zkoumání kvadratických forem a continued fractions. Jeho nejoriginálnějším činem byla 'geometry of numbers'. Toto studium vedlo k práci o konvexních objektech a k otázkám okolo packing problems. Zemřel 12. ledna 1909.
Hermann Minkowski
Minkowského operace Světlana Tomiczková
Světlana Tomiczková
21.01.2005
Použití
Rozmisťování
Rozmisťování Robot Motion Planning Offset Optics
21.01.2005
Světlana Tomiczková
Strojírenský průmysl Oděvní průmysl Obuvnický průmysl
Pojmy:
3
2
21.01.2005
Containment problem Packing problem Nesting problem Compaction Pálící programy
Světlana Tomiczková
4
1
Robot Motion Planning
Offset Ekvidistantu hraniční křivky oblasti A lze vyjádřit pomocí Minkowského sumy oblasti A a kruhu Sd se středem v počátku a poloměrem d.
Work space Configuration space Forbidden space Free space
21.01.2005
Světlana Tomiczková
5
21.01.2005
Světlana Tomiczková
6
Minkowského suma (Minkowski sum)
Optika Minkowského součin můžeme využít při hledání křivky nebo plochy, která se nazývá anticaustica.
21.01.2005
Světlana Tomiczková
7
21.01.2005
Světlana Tomiczková
8
2
Vlastnosti Minkowského sumy
21.01.2005
Světlana Tomiczková
9
21.01.2005
2D - Naivní – pro konvexní mnohoúhelníky. 1. 2. 3.
Světlana Tomiczková
10
Algoritmy pro výpočet Minkowského sumy ve
Použití pro rozmisťování a pohyb
21.01.2005
Světlana Tomiczková
11
Součet polohových vektorů vrcholů mnohoúhelníků A a B. Konvexní obal mn bodů. Výpočetní složitost O(mnlog(mn))
21.01.2005
Světlana Tomiczková
12
3
Algoritmy pro výpočet Minkowského sumy ve 2D - pro konvexní mnohoúhelníky. 1. 2. 3. 4.
Algoritmy pro výpočet Minkowského sumy ve 2D- pro nekonvexní množiny.
Suma konvexních mnohoúhelníků je konvexní mnohoúhelník. Vrcholy sumy jsou součty vrcholů. Pořadí vrcholů a hran pomocí odchylek hran původních mnohoúhelníků od pevné přímky. Složitost O(m+n).
21.01.2005
Světlana Tomiczková
13
Množiny aproximujeme mnohoúhelníky P, Q. Mnohoúhelníky P, Q rozdělíme na sjednocení disjunktních konvexních množin Pi, Qj. Vypočítáme Minkowského sumy všech dvojic Pi, Qj. Sjednocení výsledných sum. Složitost O(m2n2).
21.01.2005
Světlana Tomiczková
14
Minkowského rozdíl podle autorů R. Farouki, H. P. Moon a B. Ravani
Konvoluce (convolution)
Minkowského suma:
Minkowského rozdíl:
21.01.2005
Světlana Tomiczková
15
21.01.2005
Světlana Tomiczková
16
4
Minkowského rozdíl podle Zhenyu Li Minkowského rozdíl:
Formulace podmínky umístění jedné množiny do druhé 21.01.2005
Světlana Tomiczková
17
21.01.2005
Světlana Tomiczková
18
19
21.01.2005
Světlana Tomiczková
20
Minkowského rozdíl (Minkowski difference)
21.01.2005
Světlana Tomiczková
5
Operace Minkowského rozdíl je inverzní operací (vratná) k Minkowského sumě
Příklad:
Formulace podmínky umístění jedné množiny do druhé: 21.01.2005
Světlana Tomiczková
21
Světlana Tomiczková
Světlana Tomiczková
22
Minkowského součin (Minkowski product)
Problém Minkowského rozdílu
21.01.2005
21.01.2005
23
21.01.2005
Světlana Tomiczková
24
6
Násobení bodem
21.01.2005
Násobení dvou přímek
Světlana Tomiczková
25
Důkaz
21.01.2005
Světlana Tomiczková
26
Úpatnice a inverzní úpatnice
Pomocí násobení jednoprvkovou množinou transformujeme obě přímky do svislých přímek procházejících bodem [1, 0], tj. A={[1,t], t∈R}, B={[1,s], s∈Ρ Ρ}. Vynásobením B bodem ležícím na A, dostaneme otočenou přímku B‘, která je kolmá na přímku určenou body [0,0],[1,t]. Rovnice přímky B‘ je x + ty - t2 – 1 = 0 Jednoparametrická soustava přímek Φ(x,y,t): x + ty - t2 – 1 = 0. Derivací a eliminací t dostaneme obálku této soustavy, tj. parabolu y2 = 4( 1 - x ) … vrchol [1,0], ohnisko [0,0].
21.01.2005
Světlana Tomiczková
27
21.01.2005
Světlana Tomiczková
28
7
Násobení křivky a přímky
21.01.2005
Světlana Tomiczková
Příklad: Násobení kružnice a přímky
29
21.01.2005
Světlana Tomiczková
30
Minkowského operace v E3 (Minkowski operation in E3 )
21.01.2005
Světlana Tomiczková
31
21.01.2005
Světlana Tomiczková
32
8
Související témata:
Proč kvaterniony? Komplexní čísla nemůžeme rozšířit do E3 . Nemůžeme vytvořit algebru dimenze 3 bez dělitelů nuly. Kvaterniony tvoří algebru. Pomocí součinu kvaternionů můžeme vyjádřit otočení.
21.01.2005
Světlana Tomiczková
33
Definice dalších operací jako mocniny, odmocniny, konvoluce a akci. Algoritmy. Vlastnosti těchto operací z hlediska algebraického i geometrického. Operace v E3. Aplikace těchto operací v geometrii (nové způsoby vytvoření křivek a ploch) a v technické praxi (rozmisťování, optika). V dostupné literatuře jsou algoritmy a aplikace Minkowského operací pro lomené čáry a kuželosečky. Zajímavou možností další práce je i otázka spline a NURBS objektů v souvislosti s Minkowského operacemi – asi nelze. Blaschke sum.
21.01.2005
34
Děkuji za pozornost
Literatura
Světlana Tomiczková
Daniels, Karen McIntosh; Zhenyu Li; Milenkovic, Viktor J.: Multiple Containment Methods. Technical Report TR-12-94. Center for Research in Computing Rechnology, Harvard University, Cambridge, 1994. Farouki, Rida T.; Moon, H. P.; Ravani, B: Minkowski geometric algebra of complex sets. Geometriae Dedicata 85: 283-315, 2001. Farouki, Rida T.: Minkowski Combinations of Complex Sets. Curve and SurfaceFitting. Saint-Malo 2002. de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried: Computational geometry. Algorithms and applications. Berlin: Springer Verlag 1997. ISBN 3-540-65620-0
21.01.2005
Světlana Tomiczková
35
21.01.2005
Světlana Tomiczková
36
9
