Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Voron´ eho konstrukce na mapˇ e svˇ eta Jan Pavl´ık
´ Ustav matematiky, FSI VUT, 7. 6. 2011
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Voron´ eho konstrukce na mapˇ e svˇ eta Jan Pavl´ık
´ Ustav matematiky, FSI VUT, 7. 6. 2011
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Z´ akladn´ı myˇslenka Je d´ana koneˇcn´a mnoˇzina M bod˚ u v rovinˇe X (obecnˇe v metrick´em prostoru). Voron´ eho buˇ nka pro dan´y prvek m ∈ M - mnoˇzina vˇsech x ∈ X takov´ych, pro nˇeˇz je nejbliˇzˇs´ım prvkem z mnoˇziny M prvek m Voron´ eho diagram - rozdˇelen´ı roviny X na Voron´eho buˇ nky pro vˇsechny prvky m ∈ M http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Z´ akladn´ı myˇslenka Je d´ana koneˇcn´a mnoˇzina M bod˚ u v rovinˇe X (obecnˇe v metrick´em prostoru). Voron´ eho buˇ nka pro dan´y prvek m ∈ M - mnoˇzina vˇsech x ∈ X takov´ych, pro nˇeˇz je nejbliˇzˇs´ım prvkem z mnoˇziny M prvek m Voron´ eho diagram - rozdˇelen´ı roviny X na Voron´eho buˇ nky pro vˇsechny prvky m ∈ M http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Z´ akladn´ı myˇslenka Je d´ana koneˇcn´a mnoˇzina M bod˚ u v rovinˇe X (obecnˇe v metrick´em prostoru). Voron´ eho buˇ nka pro dan´y prvek m ∈ M - mnoˇzina vˇsech x ∈ X takov´ych, pro nˇeˇz je nejbliˇzˇs´ım prvkem z mnoˇziny M prvek m Voron´ eho diagram - rozdˇelen´ı roviny X na Voron´eho buˇ nky pro vˇsechny prvky m ∈ M http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Z´ akladn´ı myˇslenka Je d´ana koneˇcn´a mnoˇzina M bod˚ u v rovinˇe X (obecnˇe v metrick´em prostoru). Voron´ eho buˇ nka pro dan´y prvek m ∈ M - mnoˇzina vˇsech x ∈ X takov´ych, pro nˇeˇz je nejbliˇzˇs´ım prvkem z mnoˇziny M prvek m Voron´ eho diagram - rozdˇelen´ı roviny X na Voron´eho buˇ nky pro vˇsechny prvky m ∈ M http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Z´ akladn´ı myˇslenka Je d´ana koneˇcn´a mnoˇzina M bod˚ u v rovinˇe X (obecnˇe v metrick´em prostoru). Voron´ eho buˇ nka pro dan´y prvek m ∈ M - mnoˇzina vˇsech x ∈ X takov´ych, pro nˇeˇz je nejbliˇzˇs´ım prvkem z mnoˇziny M prvek m Voron´ eho diagram - rozdˇelen´ı roviny X na Voron´eho buˇ nky pro vˇsechny prvky m ∈ M http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Z´ akladn´ı myˇslenka Je d´ana koneˇcn´a mnoˇzina M bod˚ u v rovinˇe X (obecnˇe v metrick´em prostoru). Voron´ eho buˇ nka pro dan´y prvek m ∈ M - mnoˇzina vˇsech x ∈ X takov´ych, pro nˇeˇz je nejbliˇzˇs´ım prvkem z mnoˇziny M prvek m Voron´ eho diagram - rozdˇelen´ı roviny X na Voron´eho buˇ nky pro vˇsechny prvky m ∈ M http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Z´ akladn´ı myˇslenka Je d´ana koneˇcn´a mnoˇzina M bod˚ u v rovinˇe X (obecnˇe v metrick´em prostoru). Voron´ eho buˇ nka pro dan´y prvek m ∈ M - mnoˇzina vˇsech x ∈ X takov´ych, pro nˇeˇz je nejbliˇzˇs´ım prvkem z mnoˇziny M prvek m Voron´ eho diagram - rozdˇelen´ı roviny X na Voron´eho buˇ nky pro vˇsechny prvky m ∈ M http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Z´ akladn´ı myˇslenka Je d´ana koneˇcn´a mnoˇzina M bod˚ u v rovinˇe X (obecnˇe v metrick´em prostoru). Voron´ eho buˇ nka pro dan´y prvek m ∈ M - mnoˇzina vˇsech x ∈ X takov´ych, pro nˇeˇz je nejbliˇzˇs´ım prvkem z mnoˇziny M prvek m Voron´ eho diagram - rozdˇelen´ı roviny X na Voron´eho buˇ nky pro vˇsechny prvky m ∈ M http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Metody v´ ypoˇ ctu
K dan´emu prvku m0 ∈ M hled´ame jeho Voron´eho buˇ nku. Voron´ eho buˇ nka - z´ akladn´ı postup Voron´eho buˇ nku B(m0 ) dostaneme pr˚ unikem polorovin Pm0 ,m (pˇres vˇsechna m ∈ M, m 6= m0 ) urˇcen´ych pˇr´ımkami oddˇeluj´ıc´ıch dvojici (m0 , m) a obsahuj´ıc´ı prvek m0 \ B(m0 ) = Pm0 ,m m∈M,m6=m0
N´ amˇ et k zamyˇslen´ı Vymyslete lepˇs´ı algoritmus pro nalezen´ı Voron´eho buˇ nky.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Metody v´ ypoˇ ctu
K dan´emu prvku m0 ∈ M hled´ame jeho Voron´eho buˇ nku. Voron´ eho buˇ nka - z´ akladn´ı postup Voron´eho buˇ nku B(m0 ) dostaneme pr˚ unikem polorovin Pm0 ,m (pˇres vˇsechna m ∈ M, m 6= m0 ) urˇcen´ych pˇr´ımkami oddˇeluj´ıc´ıch dvojici (m0 , m) a obsahuj´ıc´ı prvek m0 \ B(m0 ) = Pm0 ,m m∈M,m6=m0
N´ amˇ et k zamyˇslen´ı Vymyslete lepˇs´ı algoritmus pro nalezen´ı Voron´eho buˇ nky.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Metody v´ ypoˇ ctu
K dan´emu prvku m0 ∈ M hled´ame jeho Voron´eho buˇ nku. Voron´ eho buˇ nka - z´ akladn´ı postup Voron´eho buˇ nku B(m0 ) dostaneme pr˚ unikem polorovin Pm0 ,m (pˇres vˇsechna m ∈ M, m 6= m0 ) urˇcen´ych pˇr´ımkami oddˇeluj´ıc´ıch dvojici (m0 , m) a obsahuj´ıc´ı prvek m0 \ B(m0 ) = Pm0 ,m m∈M,m6=m0
N´ amˇ et k zamyˇslen´ı Vymyslete lepˇs´ı algoritmus pro nalezen´ı Voron´eho buˇ nky.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Metody v´ ypoˇ ctu
K dan´emu prvku m0 ∈ M hled´ame jeho Voron´eho buˇ nku. Voron´ eho buˇ nka - z´ akladn´ı postup Voron´eho buˇ nku B(m0 ) dostaneme pr˚ unikem polorovin Pm0 ,m (pˇres vˇsechna m ∈ M, m 6= m0 ) urˇcen´ych pˇr´ımkami oddˇeluj´ıc´ıch dvojici (m0 , m) a obsahuj´ıc´ı prvek m0 \ B(m0 ) = Pm0 ,m m∈M,m6=m0
N´ amˇ et k zamyˇslen´ı Vymyslete lepˇs´ı algoritmus pro nalezen´ı Voron´eho buˇ nky.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Oddˇ eluj´ıc´ı pˇr´ımka Z´akladn´ım stavebn´ım prvkem pro konstrukci Voron´eho buˇ nky je oddˇeluj´ıc´ı pˇr´ımka neboli bisektor a j´ı (a bodem) urˇcen´a polorovina. Z´ akladn´ı probl´ em Jsou d´any body X a Y v z´akladn´ım prostoru P. Hled´ame jejich oddˇeluj´ıc´ı pˇr´ımku p a j´ı a bodem X urˇcenou polorovinu πX . Konstrukce Body X a Y vedeme pˇr´ımku q,vznikne u ´seˇcka XY ,najdeme jej´ı stˇred S.Pˇr´ımka p je kolmice na q veden´a bodem S. Tato pˇr´ımka rozdˇeluje prostor P na dvˇe ˇc´asti, poloroviny πX , resp. πY , v nichˇz leˇz´ı body X , resp. Y . Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Oddˇ eluj´ıc´ı pˇr´ımka Z´akladn´ım stavebn´ım prvkem pro konstrukci Voron´eho buˇ nky je oddˇeluj´ıc´ı pˇr´ımka neboli bisektor a j´ı (a bodem) urˇcen´a polorovina. Z´ akladn´ı probl´ em Jsou d´any body X a Y v z´akladn´ım prostoru P. Hled´ame jejich oddˇeluj´ıc´ı pˇr´ımku p a j´ı a bodem X urˇcenou polorovinu πX . Konstrukce Body X a Y vedeme pˇr´ımku q,vznikne u ´seˇcka XY ,najdeme jej´ı stˇred S.Pˇr´ımka p je kolmice na q veden´a bodem S. Tato pˇr´ımka rozdˇeluje prostor P na dvˇe ˇc´asti, poloroviny πX , resp. πY , v nichˇz leˇz´ı body X , resp. Y . Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Oddˇ eluj´ıc´ı pˇr´ımka Z´akladn´ım stavebn´ım prvkem pro konstrukci Voron´eho buˇ nky je oddˇeluj´ıc´ı pˇr´ımka neboli bisektor a j´ı (a bodem) urˇcen´a polorovina. Z´ akladn´ı probl´ em Jsou d´any body X a Y v z´akladn´ım prostoru P. Hled´ame jejich oddˇeluj´ıc´ı pˇr´ımku p a j´ı a bodem X urˇcenou polorovinu πX . Konstrukce Body X a Y vedeme pˇr´ımku q,vznikne u ´seˇcka XY ,najdeme jej´ı stˇred S.Pˇr´ımka p je kolmice na q veden´a bodem S. Tato pˇr´ımka rozdˇeluje prostor P na dvˇe ˇc´asti, poloroviny πX , resp. πY , v nichˇz leˇz´ı body X , resp. Y . Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Oddˇ eluj´ıc´ı pˇr´ımka Z´akladn´ım stavebn´ım prvkem pro konstrukci Voron´eho buˇ nky je oddˇeluj´ıc´ı pˇr´ımka neboli bisektor a j´ı (a bodem) urˇcen´a polorovina. Z´ akladn´ı probl´ em Jsou d´any body X a Y v z´akladn´ım prostoru P. Hled´ame jejich oddˇeluj´ıc´ı pˇr´ımku p a j´ı a bodem X urˇcenou polorovinu πX . Konstrukce Body X a Y vedeme pˇr´ımku q,vznikne u ´seˇcka XY ,najdeme jej´ı stˇred S.Pˇr´ımka p je kolmice na q veden´a bodem S. Tato pˇr´ımka rozdˇeluje prostor P na dvˇe ˇc´asti, poloroviny πX , resp. πY , v nichˇz leˇz´ı body X , resp. Y . Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Oddˇ eluj´ıc´ı pˇr´ımka Z´akladn´ım stavebn´ım prvkem pro konstrukci Voron´eho buˇ nky je oddˇeluj´ıc´ı pˇr´ımka neboli bisektor a j´ı (a bodem) urˇcen´a polorovina. Z´ akladn´ı probl´ em Jsou d´any body X a Y v z´akladn´ım prostoru P. Hled´ame jejich oddˇeluj´ıc´ı pˇr´ımku p a j´ı a bodem X urˇcenou polorovinu πX . Konstrukce Body X a Y vedeme pˇr´ımku q,vznikne u ´seˇcka XY ,najdeme jej´ı stˇred S.Pˇr´ımka p je kolmice na q veden´a bodem S. Tato pˇr´ımka rozdˇeluje prostor P na dvˇe ˇc´asti, poloroviny πX , resp. πY , v nichˇz leˇz´ı body X , resp. Y . Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Oddˇ eluj´ıc´ı pˇr´ımka Z´akladn´ım stavebn´ım prvkem pro konstrukci Voron´eho buˇ nky je oddˇeluj´ıc´ı pˇr´ımka neboli bisektor a j´ı (a bodem) urˇcen´a polorovina. Z´ akladn´ı probl´ em Jsou d´any body X a Y v z´akladn´ım prostoru P. Hled´ame jejich oddˇeluj´ıc´ı pˇr´ımku p a j´ı a bodem X urˇcenou polorovinu πX . Konstrukce Body X a Y vedeme pˇr´ımku q,vznikne u ´seˇcka XY ,najdeme jej´ı stˇred S.Pˇr´ımka p je kolmice na q veden´a bodem S. Tato pˇr´ımka rozdˇeluje prostor P na dvˇe ˇc´asti, poloroviny πX , resp. πY , v nichˇz leˇz´ı body X , resp. Y . Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Oddˇ eluj´ıc´ı pˇr´ımka Z´akladn´ım stavebn´ım prvkem pro konstrukci Voron´eho buˇ nky je oddˇeluj´ıc´ı pˇr´ımka neboli bisektor a j´ı (a bodem) urˇcen´a polorovina. Z´ akladn´ı probl´ em Jsou d´any body X a Y v z´akladn´ım prostoru P. Hled´ame jejich oddˇeluj´ıc´ı pˇr´ımku p a j´ı a bodem X urˇcenou polorovinu πX . Konstrukce Body X a Y vedeme pˇr´ımku q,vznikne u ´seˇcka XY ,najdeme jej´ı stˇred S.Pˇr´ımka p je kolmice na q veden´a bodem S. Tato pˇr´ımka rozdˇeluje prostor P na dvˇe ˇc´asti, poloroviny πX , resp. πY , v nichˇz leˇz´ı body X , resp. Y . Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Sf´ erick´ e konstrukce
Sf´ erick´ a geometrie prostor P– kulov´a plocha se stˇredem C o polomˇeru r pˇr´ımka – hlavn´ı kruˇznice sf´ery P (kruˇznice stˇredem C o polomˇeru r ) u ´seˇ cka – ublouk hlavn´ı kruˇznice stˇred u ´seˇ cky – bod na u ´seˇcce urˇcen´y poloviˇcn´ım stˇredov´ym u ´hlem u ´hel pˇr´ımek – u ´hel pˇr´ısluˇsn´ych rovin Takto ch´apan´e pojmy n´am umoˇzn´ı konstrukci oddˇeluj´ıc´ı pˇr´ımky, poloroviny a tedy i Voron´eho buˇ nky ve sf´erick´e geometrii. To m˚ uˇzeme pouˇz´ıt pro urˇcen´ı oblasti v´yznamu.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Sf´ erick´ e konstrukce
Sf´ erick´ a geometrie prostor P– kulov´a plocha se stˇredem C o polomˇeru r pˇr´ımka – hlavn´ı kruˇznice sf´ery P (kruˇznice stˇredem C o polomˇeru r ) u ´seˇ cka – ublouk hlavn´ı kruˇznice stˇred u ´seˇ cky – bod na u ´seˇcce urˇcen´y poloviˇcn´ım stˇredov´ym u ´hlem u ´hel pˇr´ımek – u ´hel pˇr´ısluˇsn´ych rovin Takto ch´apan´e pojmy n´am umoˇzn´ı konstrukci oddˇeluj´ıc´ı pˇr´ımky, poloroviny a tedy i Voron´eho buˇ nky ve sf´erick´e geometrii. To m˚ uˇzeme pouˇz´ıt pro urˇcen´ı oblasti v´yznamu.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Sf´ erick´ e konstrukce
Sf´ erick´ a geometrie prostor P– kulov´a plocha se stˇredem C o polomˇeru r pˇr´ımka – hlavn´ı kruˇznice sf´ery P (kruˇznice stˇredem C o polomˇeru r ) u ´seˇ cka – ublouk hlavn´ı kruˇznice stˇred u ´seˇ cky – bod na u ´seˇcce urˇcen´y poloviˇcn´ım stˇredov´ym u ´hlem u ´hel pˇr´ımek – u ´hel pˇr´ısluˇsn´ych rovin Takto ch´apan´e pojmy n´am umoˇzn´ı konstrukci oddˇeluj´ıc´ı pˇr´ımky, poloroviny a tedy i Voron´eho buˇ nky ve sf´erick´e geometrii. To m˚ uˇzeme pouˇz´ıt pro urˇcen´ı oblasti v´yznamu.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Sf´ erick´ e konstrukce
Sf´ erick´ a geometrie prostor P– kulov´a plocha se stˇredem C o polomˇeru r pˇr´ımka – hlavn´ı kruˇznice sf´ery P (kruˇznice stˇredem C o polomˇeru r ) u ´seˇ cka – ublouk hlavn´ı kruˇznice stˇred u ´seˇ cky – bod na u ´seˇcce urˇcen´y poloviˇcn´ım stˇredov´ym u ´hlem u ´hel pˇr´ımek – u ´hel pˇr´ısluˇsn´ych rovin Takto ch´apan´e pojmy n´am umoˇzn´ı konstrukci oddˇeluj´ıc´ı pˇr´ımky, poloroviny a tedy i Voron´eho buˇ nky ve sf´erick´e geometrii. To m˚ uˇzeme pouˇz´ıt pro urˇcen´ı oblasti v´yznamu.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Sf´ erick´ e konstrukce
Sf´ erick´ a geometrie prostor P– kulov´a plocha se stˇredem C o polomˇeru r pˇr´ımka – hlavn´ı kruˇznice sf´ery P (kruˇznice stˇredem C o polomˇeru r ) u ´seˇ cka – ublouk hlavn´ı kruˇznice stˇred u ´seˇ cky – bod na u ´seˇcce urˇcen´y poloviˇcn´ım stˇredov´ym u ´hlem u ´hel pˇr´ımek – u ´hel pˇr´ısluˇsn´ych rovin Takto ch´apan´e pojmy n´am umoˇzn´ı konstrukci oddˇeluj´ıc´ı pˇr´ımky, poloroviny a tedy i Voron´eho buˇ nky ve sf´erick´e geometrii. To m˚ uˇzeme pouˇz´ıt pro urˇcen´ı oblasti v´yznamu.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Sf´ erick´ e konstrukce
Sf´ erick´ a geometrie prostor P– kulov´a plocha se stˇredem C o polomˇeru r pˇr´ımka – hlavn´ı kruˇznice sf´ery P (kruˇznice stˇredem C o polomˇeru r ) u ´seˇ cka – ublouk hlavn´ı kruˇznice stˇred u ´seˇ cky – bod na u ´seˇcce urˇcen´y poloviˇcn´ım stˇredov´ym u ´hlem u ´hel pˇr´ımek – u ´hel pˇr´ısluˇsn´ych rovin Takto ch´apan´e pojmy n´am umoˇzn´ı konstrukci oddˇeluj´ıc´ı pˇr´ımky, poloroviny a tedy i Voron´eho buˇ nky ve sf´erick´e geometrii. To m˚ uˇzeme pouˇz´ıt pro urˇcen´ı oblasti v´yznamu.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Sf´ erick´ e konstrukce
Sf´ erick´ a geometrie prostor P– kulov´a plocha se stˇredem C o polomˇeru r pˇr´ımka – hlavn´ı kruˇznice sf´ery P (kruˇznice stˇredem C o polomˇeru r ) u ´seˇ cka – ublouk hlavn´ı kruˇznice stˇred u ´seˇ cky – bod na u ´seˇcce urˇcen´y poloviˇcn´ım stˇredov´ym u ´hlem u ´hel pˇr´ımek – u ´hel pˇr´ısluˇsn´ych rovin Takto ch´apan´e pojmy n´am umoˇzn´ı konstrukci oddˇeluj´ıc´ı pˇr´ımky, poloroviny a tedy i Voron´eho buˇ nky ve sf´erick´e geometrii. To m˚ uˇzeme pouˇz´ıt pro urˇcen´ı oblasti v´yznamu.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Tvorba oblast´ı v´ yznamu
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Oblast v´yznamu Brna (dle populace).
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Pˇribliˇzn´a oblast v´yznamu Snˇeˇzky (dle nadmoˇrsk´e v´yˇsky).
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Kruˇznicov´y algoritmus pro upˇresnˇen´ı oblasti v´yznamu.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Zde hled´ame nov´y urˇcuj´ıc´ı vrchol.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Oblast v´yznamu Snˇeˇzky po u ´pravˇe.
Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Voron´ eho diagram V´ypoˇcet Voron´eho diagramu postupnou konstrukc´ı jednotliv´ych buˇ nek by urˇcitˇe nebyl nejvhodnˇejˇs´ı. Existuj´ı proto jin´e algoritmy, kter´e vyuˇz´ıvaj´ı vlastnost´ı diagramu jako celku (pomoc´ı tzv. pˇr´ıbojov´e vlny nebo Delauneyovy triangulace). Sloˇ zitost algoritmu V´ypoˇcet Voron´eho diagramu je nejrychlejˇs´ı Fortunov´ym algoritmem pomoc´ı tzv. pˇr´ıbojov´e vlny http://en.wikipedia.org/wiki/Fortune’s_algorithm Algoritmus poˇc´ıt´a v ˇcase O(n log n) pˇri n prvc´ıch mnoˇziny M.
Literatura Berg, Cheong, Kreveld, Overmars: Computational Geometry, Springer Verlag 1997 Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Voron´ eho diagram V´ypoˇcet Voron´eho diagramu postupnou konstrukc´ı jednotliv´ych buˇ nek by urˇcitˇe nebyl nejvhodnˇejˇs´ı. Existuj´ı proto jin´e algoritmy, kter´e vyuˇz´ıvaj´ı vlastnost´ı diagramu jako celku (pomoc´ı tzv. pˇr´ıbojov´e vlny nebo Delauneyovy triangulace). Sloˇ zitost algoritmu V´ypoˇcet Voron´eho diagramu je nejrychlejˇs´ı Fortunov´ym algoritmem pomoc´ı tzv. pˇr´ıbojov´e vlny http://en.wikipedia.org/wiki/Fortune’s_algorithm Algoritmus poˇc´ıt´a v ˇcase O(n log n) pˇri n prvc´ıch mnoˇziny M.
Literatura Berg, Cheong, Kreveld, Overmars: Computational Geometry, Springer Verlag 1997 Pavl´ık
Voron´ eho konstrukce
Voron´ eho diagramy Sf´ erick´ e konstrukce Fortun˚ uv algoritmus
Voron´ eho diagram V´ypoˇcet Voron´eho diagramu postupnou konstrukc´ı jednotliv´ych buˇ nek by urˇcitˇe nebyl nejvhodnˇejˇs´ı. Existuj´ı proto jin´e algoritmy, kter´e vyuˇz´ıvaj´ı vlastnost´ı diagramu jako celku (pomoc´ı tzv. pˇr´ıbojov´e vlny nebo Delauneyovy triangulace). Sloˇ zitost algoritmu V´ypoˇcet Voron´eho diagramu je nejrychlejˇs´ı Fortunov´ym algoritmem pomoc´ı tzv. pˇr´ıbojov´e vlny http://en.wikipedia.org/wiki/Fortune’s_algorithm Algoritmus poˇc´ıt´a v ˇcase O(n log n) pˇri n prvc´ıch mnoˇziny M.
Literatura Berg, Cheong, Kreveld, Overmars: Computational Geometry, Springer Verlag 1997 Pavl´ık
Voron´ eho konstrukce
