VORONÉHO DIAGRAMY

Oldřich Petřík

HISTORIE

1644: René Descartes

dílo Principy filosofie

rozložení hmoty ve Sluneční soustavě

1850: Johann Dirichlet

studium kvadratických forem

1854: John Snow

rozšíření cholery v Soho

2

HISTORIE

1908: Georgij Voronoj

profesor na

Varšavské univerzitě

zájem o algebru

a geometrii čísel

zobecnění diagramu

v prostoru o n rozměrech

3

DEFINICE

Oblast

množina bodů nejblíže k danému bodu

vzdálenost euklidovská

hraniční oblasti – otevřené

vnitřní oblasti – konvexní mnohoúhelníky

Diagram

hranice oblastí

hrany a vrcholy diagramu

4

VZHLED DIAGRAMŮ

Dva body

poloroviny oddělené osou spojnice

Tři body

na kružnici nebo kolineární

Vícebodová množina

průnik n-1 polorovin

body konvexního obalu = otevřené oblasti

5

VZHLED DIAGRAMŮ

6

VZHLED DIAGRAMŮ

Speciální případy

body na přímce

rovnoběžky, nejsou vrcholy

body na kružnici

polopřímky se společným počátkem

pravidelně rozložené body

trojúhelníková síť

obdélníková síť

šestiúhelníková síť

7

KONSTRUKCE

Z definice (průnik polorovin)

Inkrementální

Rozděl a panuj

Fortunův algoritmus

Metoda zdvihu

Z Delaunayovy triangulace

Pomocí kružnic

8

DELAUNAYOVA TRIANGULACE

Duální k Voroného diagramu

body sousedních oblastí sdílí hranu v DT

v opsané kružnici trojúhelníků žádný další bod

nejednoznačnosti – více bodů na kružnici

Maximalizuje minimální úhel

trojúhelníky nejblíže

rovnostranným

9

ZOBECNĚNÍ

Přidání vah k bodům

diagram složen z částí kružnic a přímek

Zobecnění generující množiny

úsečky, kružnice, polygony, …

Změna metriky

např. L1 metrika

oblasti již nemusí být konvexní

Pohyb bodů

jeden bod × všechny body10

POUŽITÍ

Počítačová grafika

hledání nejbližších sousedů a shluků

klasifikace objektů v obraze

konstrukce Delaunayovy triangulace

mozaiky

11

POUŽITÍ

Geometrické problémy

nalezení nejkratší cesty

problém největšího toku

uspořádání kabelů do svazku

aproximace minimum spanning tree

aproximace problému obchodního cestujícího

problém největší kružnice

problém nejbližší pošty

12

POUŽITÍ

Problém nejbližší pošty

13

POUŽITÍ

Kybernetika

plánování cesty robota mezi překážkami

zobecněný Voroného diagram

překážky = generující množina

hrany diagramu určují ideální dráhu

14

POUŽITÍ

Výskyt v přírodních jevech

teritoria zvířat

rozšíření rostlin

buněčná struktura

včelí plástve

koráli

růst krystalů

rozmístění molekul

15

DĚKUJI ZA POZORNOST!

16