Voronoi Diagram (4/5) | Computational Geometry

Voronoi Diagram (4/5) | Computational Geometry - Lecture 07

Рет қаралды 13,978

4 жыл бұрын

Computational Geometry
Lecture 07: Voronoi Diagram
Part IV: The Beachline
Philipp Kindermann
Desmos Animation: desmos.com/calculator/0b96jkosm2
Beachline Animation: • Sweep line algorithm -...
Playlist: • Voronoi Diagrams | Com...
Slides: algo.uni-trier.de/lectures/al...
Full course: / @philippkindermann

Пікірлер: 15

@BehavingBeaver 3 жыл бұрын

Finally someone explains this in a good manner. Awesome video, thanks

@finn9233 2 жыл бұрын

wow the beachline concept is just beautiful, it all comes together!

@micmacha 2 жыл бұрын

What a wonderful explanation of Fortune's algorithm. Thank you sir.

@Z3rgatul 2 жыл бұрын

Cool, understood more from this 10 minutes video, than from hours of reading related books

@MyProceduralMap Жыл бұрын

Philipp TY SO MUCH!!!!

@iit_da_munda 2 жыл бұрын

great video!

@iit_da_munda 2 жыл бұрын

Is there any video for devide and conquer algo?

@andreytrushnikov2164 3 жыл бұрын

Hi Philipp Kindermann. Do you know how to build voronoi diagrams using fast marching ?

@PhilippKindermann 3 жыл бұрын

Unfortunately not, sorry :(

@coalbl4ck Жыл бұрын

Hi, do you by chance remember how the runtime for calculating the voronoi-diagram with the line-segment algorithm results in O(n (log n)**2) time? :)

@PhilippKindermann 11 ай бұрын

Hey, sorry this is an error on the slides; the line-segment algorithm would take O(n^2 log n) time since there are n^2 many half-planes. That's why the runtime in total is then O(n^2 log n).

@empireempire3545 2 жыл бұрын

Hi - are you aware of a way to compute a new voronoi diagram when the positions of all points have been pertured slightly and you already have the diagram calculated before hte perturbation? Imagine for example watching a movie of billard balls or gas particles moving in slow motion and you want to have voronoi diagram for each frame - computing voronoi diagram from scratch for each frame doesnt seem like a very efficient approach and it seems to me that there should be a way to recompute the diagram based on the diagram from the previous frame.

@PhilippKindermann 2 жыл бұрын

Hey, this might be what you are looking for: Chanyoung Song, Jehyun Cha, Mokwon Lee, Deok-Soo Kim: Dynamic Voronoi Diagram for Moving Disks. IEEE Trans. Vis. Comput. Graph. 27(6): 2923-2940 (2021) ieeexplore.ieee.org/document/8933488

@empireempire3545 2 жыл бұрын

@@PhilippKindermann Wow that was quick, thanks :D

@empireempire3545 2 жыл бұрын

@@PhilippKindermann This one is for disks though! Well, perhaps the 'billard balls' example was misleading in that regard. Still, thank You ; )