Geometria

Geometria

Obliczeniowa

Obliczeniowa

Diagramy Voronoi

Diagramy Voronoi

Krzysztof Piecuch

Krzysztof Piecuch

IIC

IIC

1

1

Geometria

Geometria

Obliczeniowa

Obliczeniowa

Część I: Zestaw

Część I: Zestaw

problemów

problemów

Problem 1 (Najbliższa para)

Problem 1 (Najbliższa para)



Jeśli danych jest N punktów na

Jeśli danych jest N punktów na

płaszczyźnie, znaleźć dwa punkty,

płaszczyźnie, znaleźć dwa punkty,

których wzajemna odległość jest

których wzajemna odległość jest

najmniejsza.

najmniejsza.



Zasadnicze pytanie geometrii

Zasadnicze pytanie geometrii

obliczeniowej

obliczeniowej



Problem kontroli lotów

Problem kontroli lotów



Czy konieczne jest badanie każdej

Czy konieczne jest badanie każdej

pary punktów?

pary punktów?

Problem 2 (Wszystkie pary)

Problem 2 (Wszystkie pary)



Jeśli danych jest N punktów na

Jeśli danych jest N punktów na

płaszczyźnie, znaleźć dla każdego

płaszczyźnie, znaleźć dla każdego

z nich najbliższego sąsiada.

z nich najbliższego sąsiada.



Relacja nie musi być symetryczna

Relacja nie musi być symetryczna



1

1

punkt może mieć wiele

punkt może mieć wiele

takich

takich

sąsiadów

sąsiadów



Pary wzajemne

Pary wzajemne

Zastosowania: ekologia matematyczna, geografia, fizyka bryły

Zastosowania: ekologia matematyczna, geografia, fizyka bryły

sztywnej

sztywnej

Problem 3 (EMST)

Problem 3 (EMST)



Jeśli danych jest N punktów na

Jeśli danych jest N punktów na

płaszczyźnie, stworzyć drzewo o

płaszczyźnie, stworzyć drzewo o

najmniejszej całkowitej długości,

najmniejszej całkowitej długości,

którego wierzchołki są danymi punktami

którego wierzchołki są danymi punktami



Drzewo Steinera (problem klasy NP)

Drzewo Steinera (problem klasy NP)



MST zawiera najkrótszą krawędź

MST zawiera najkrótszą krawędź



Problem Euklidesowy jest mocno ogr.

Problem Euklidesowy jest mocno ogr.

Zastosowania: klastrowanie, wyznaczanie wymiaru zbioru punktów,

Zastosowania: klastrowanie, wyznaczanie wymiaru zbioru punktów,

rozpoznawanie wzorca, minimalizacja długości obwodu w układach

rozpoznawanie wzorca, minimalizacja długości obwodu w układach

komputerowych, podstawy do badań nad problemem komiwojażera

komputerowych, podstawy do badań nad problemem komiwojażera

Problem 4 (Wypukła otoczka)

Problem 4 (Wypukła otoczka)



Mając dany zbiór S złożony z N

Mając dany zbiór S złożony z N

punktów na płaszczyźnie, znaleźć

punktów na płaszczyźnie, znaleźć

najmniejszy zbiór wypukły

najmniejszy zbiór wypukły

zawierający wszystkie punkty

zawierający wszystkie punkty

zbioru S. Conv(S)

zbioru S. Conv(S)



Kluczowe zagadnienie wielu

Kluczowe zagadnienie wielu

problemów geometrii obliczeniowej

problemów geometrii obliczeniowej

Zastosowania: rozpoznawanie wzorców, cięcia, rozlokowywanie

Zastosowania: rozpoznawanie wzorców, cięcia, rozlokowywanie

towarów, statystyka (regresja liniowa, regresja izotoniczna, teoria

towarów, statystyka (regresja liniowa, regresja izotoniczna, teoria

głosowania, klastrowanie (średnica zbioru punktów)) i wiele wiele

głosowania, klastrowanie (średnica zbioru punktów)) i wiele wiele

innych.

innych.

Problem 5 (Triangulacja)

Problem 5 (Triangulacja)



Jeśli danych jest N punktów na

Jeśli danych jest N punktów na

płaszczyźnie połączyć je nie

płaszczyźnie połączyć je nie

przecinającymi się odcinkami tak,

przecinającymi się odcinkami tak,

aby każdy obszar wewnątrz

aby każdy obszar wewnątrz

wypukłej otoczki był trójkątem.

wypukłej otoczki był trójkątem.

Zastosowania: metoda elementu skończonego, numeryczna

Zastosowania: metoda elementu skończonego, numeryczna

interpolacja danych dwuzmiennych

interpolacja danych dwuzmiennych

Problem 6 (Szukanie sąsiada)

Problem 6 (Szukanie sąsiada)



Jeśli danych jest N punktów na

Jeśli danych jest N punktów na

płaszczyźnie i jeśli możliwe jest

płaszczyźnie i jeśli możliwe jest

przetwarzanie wstępne, jak szybko

przetwarzanie wstępne, jak szybko

znaleźć najbliższego sąsiada

znaleźć najbliższego sąsiada

nowego danego punktu q.

nowego danego punktu q.

Zastosowania: problem klasyfikacji, rozpoznawanie mowy,

Zastosowania: problem klasyfikacji, rozpoznawanie mowy,

identyfikacja cząstek elementarnych, pobieranie zapisu najlepiej

identyfikacja cząstek elementarnych, pobieranie zapisu najlepiej

pasującego

pasującego

Problem 7 (k sąsiadów)

Problem 7 (k sąsiadów)



Jeśli danych jest N punktów na

Jeśli danych jest N punktów na

płaszczyźnie i dopuszczalne jest

płaszczyźnie i dopuszczalne jest

przetwarzanie wstępne, jak szybko

przetwarzanie wstępne, jak szybko

znaleźć k punktów najbliższych

znaleźć k punktów najbliższych

danemu punktowi q

danemu punktowi q

Zastosowania: interpolacja, wyznaczanie konturu, klasyfikacja

Zastosowania: interpolacja, wyznaczanie konturu, klasyfikacja

Geometria

Geometria

Obliczeniowa

Obliczeniowa

Część II: Diagramy

Część II: Diagramy

Voronoi

Voronoi

Diagram Voronoi

Diagram Voronoi



Obszary Dirichleta

Obszary Dirichleta



Wielokąty Thiessena

Wielokąty Thiessena



Komórki Wignera-Seitza

Komórki Wignera-Seitza



Wielokąty Sąsiedztwa (Dan Hoey)

Wielokąty Sąsiedztwa (Dan Hoey)

Definicja

Definicja



Niech dany będzie zbiór S N punktów.

Niech dany będzie zbiór S N punktów.



Wielokątem Voronoi związanym z p

Wielokątem Voronoi związanym z p

i

i

nazywamy zbiór wszystkich punktów

nazywamy zbiór wszystkich punktów

(x, y) takich, że są one bliżej p

(x, y) takich, że są one bliżej p

i

i

niż

niż

jakikolwiek inny punkt w S. V(i).

jakikolwiek inny punkt w S. V(i).



Diagramem Voronoi nazywamy sieć

Diagramem Voronoi nazywamy sieć

wszystkich N wielokątów Voronoi

wszystkich N wielokątów Voronoi

Vor(S)

Vor(S)

Analiza struktury

Analiza struktury

diagramu

diagramu



Jeśli dane są dwa punkty p

Jeśli dane są dwa punkty p

i

i

oraz p

oraz p

j

j

to

to

zbiór punktów bliższych p

zbiór punktów bliższych p

i

i

niż p

niż p

j

j

to

to

półpłaszczyzna zawierająca p

półpłaszczyzna zawierająca p

i

i

wyznaczona przez prostopadłą prostą

wyznaczona przez prostopadłą prostą

dzielącą na pół odcinek p

dzielącą na pół odcinek p

i

i

p

p

j

j

. Oznaczamy

. Oznaczamy

taką półpłaszczyzną przez H(p

taką półpłaszczyzną przez H(p

i

i

, p

, p

j

j

).

).

V i= ∩

i≠ j

H p

i

, p

j



Wielokąt Voronoi

Wielokąt Voronoi

Diagram Voronoi

Diagram Voronoi

Geometria

Geometria

Obliczeniowa

Obliczeniowa

Część III: Własności

Część III: Własności

Diagramów Voronoi

Diagramów Voronoi

Dodatkowe założenie

Dodatkowe założenie



Żadne cztery punkty pierwotnego

Żadne cztery punkty pierwotnego

zbioru S nie leżą na obwodzie

zbioru S nie leżą na obwodzie

jednego koła.

jednego koła.



Jeśli założenie to nie jest spełnione,

Jeśli założenie to nie jest spełnione,

konieczne jest dodawanie do

konieczne jest dodawanie do

stwierdzeń dowodów twierdzeń

stwierdzeń dowodów twierdzeń

długich, choć niewiele wnoszących

długich, choć niewiele wnoszących

uzupełnień.

uzupełnień.

Twierdzenie 1

Twierdzenie 1



Każdy węzeł diagramu Voronoi jest

Każdy węzeł diagramu Voronoi jest

wspólnym przecięciem dokładnie

wspólnym przecięciem dokładnie

trzech krawędzi diagramu.

trzech krawędzi diagramu.

Twierdzenie 2

Twierdzenie 2



Dla każdego węzła v diagramu

Dla każdego węzła v diagramu

Voronoi zbioru S okrąg C(v) nie

Voronoi zbioru S okrąg C(v) nie

zawiera żadnych innych punktów

zawiera żadnych innych punktów

S.

S.

Twierdzenie 3

Twierdzenie 3



Każdy najbliższy sąsiad p

Każdy najbliższy sąsiad p

i

i

z S

z S

definiuje krawędź wielokąta

definiuje krawędź wielokąta

Voronoi V(i).

Voronoi V(i).

Twierdzenie 4

Twierdzenie 4



Wielokąt V(i) jest nieograniczony

Wielokąt V(i) jest nieograniczony

wtedy i tylko wtedy, gdy p

wtedy i tylko wtedy, gdy p

i

i

jest

jest

punktem na brzegu otoczki

punktem na brzegu otoczki

wypukłej zbioru S.

wypukłej zbioru S.

Twierdzenie 5

Twierdzenie 5



Prosta dualna diagramu Voronoi

Prosta dualna diagramu Voronoi

jest triangulacją.

jest triangulacją.



W tej prostej postaci twierdzenie to

W tej prostej postaci twierdzenie to

zawodzi, jeśli pewne podzbiory

zawodzi, jeśli pewne podzbiory

czterech lub więcej punktów leżą

czterech lub więcej punktów leżą

na jednym okręgu. W takim

na jednym okręgu. W takim

przypadku jednak uzupełnienie

przypadku jednak uzupełnienie

triangulacji jest proste.

triangulacji jest proste.

Twierdzenie 6

Twierdzenie 6



Diagram Voronoi dla N punktów

Diagram Voronoi dla N punktów

ma co najwyżej 2N-5 węzłów i 3N-6

ma co najwyżej 2N-5 węzłów i 3N-6

krawędzi.

krawędzi.

Geometria

Geometria

Obliczeniowa

Obliczeniowa

Część IV: Tworzenie

Część IV: Tworzenie

Diagramów Voronoi

Diagramów Voronoi

Tworzenie diagramu

Tworzenie diagramu

Voronoi

Voronoi



Struktura danych: DCEL

Struktura danych: DCEL



Czas tworzenia pojedynczego

Czas tworzenia pojedynczego

wielokąta wynosi O(N log N).

wielokąta wynosi O(N log N).



Czy na stworzenie całego

Czy na stworzenie całego

diagramu potrzebujemy O(N

diagramu potrzebujemy O(N

2

2

log

log

N)?

N)?



Metoda dziel i rządź

Metoda dziel i rządź

Zastosowania: archeologia, ekologia, leśnictwo, fizyka cząstek

Zastosowania: archeologia, ekologia, leśnictwo, fizyka cząstek

elementarnych, badanie konkurujących ze sobą centrów handlowych.

elementarnych, badanie konkurujących ze sobą centrów handlowych.

Struktura danych: DCEL

Struktura danych: DCEL



V

V

1

1

– początek, V

– początek, V

2

2

– koniec krawędzi

– koniec krawędzi



F

F

1

1

– nazwa leżąca na lewo F

– nazwa leżąca na lewo F

2

2

– na

– na

prawo od krawędzi.

prawo od krawędzi.



P

P

1

1

– wskazuje węzeł krawędzi,

– wskazuje węzeł krawędzi,

zawierający pierwszą krawędź

zawierający pierwszą krawędź

znajdującą się za (V

znajdującą się za (V

1

1

, V

, V

2

2

) w kier.

) w kier.

przeciwnym do ruchu wz.

przeciwnym do ruchu wz.

Szkic algorytmu

Szkic algorytmu



Dzielimy S na dwa podzbiory, S

Dzielimy S na dwa podzbiory, S

1

1

oraz S

oraz S

2

2

, o mniej więcej równej

, o mniej więcej równej

wielkości.

wielkości.



Tworzymy rekurencyjnie Vor(S

Tworzymy rekurencyjnie Vor(S

1

1

) i

) i

Vor(S

Vor(S

2

2

).

).



Łączymy Vor(S

Łączymy Vor(S

1

1

) i Vor(S

) i Vor(S

2

2

), aby

), aby

uzyskać Vor(S).

uzyskać Vor(S).

Dlaczego ma to w ogóle

Dlaczego ma to w ogóle

działać?

działać?



Dlaczego mamy sądzić, że Vor(S

Dlaczego mamy sądzić, że Vor(S

1

1

)

)

oraz Vor(S

oraz Vor(S

2

2

) są powiązane z Vor(S)?

) są powiązane z Vor(S)?



Jeśli dany jest podział {S

Jeśli dany jest podział {S

1

1

, S

, S

2

2

} zbioru

} zbioru

S, niech

S, niech

ζ

ζ

(S

(S

1

1

, S

, S

2

2

) oznacza zbiór

) oznacza zbiór

krawędzi Voronoi wspólnych dla par

krawędzi Voronoi wspólnych dla par

wielokątów V(i) oraz V(j) diagramu

wielokątów V(i) oraz V(j) diagramu

Vor(S) dla p

Vor(S) dla p

i

i

należącego do S

należącego do S

1

1

oraz p

oraz p

j

j

należącego do S

należącego do S

2

2

.

.

Dlaczego ma to w ogóle

Dlaczego ma to w ogóle

działać?

działać?



ζ

ζ

(S

(S

1

1

, S

, S

2

2

) składa się z cykli i łańcuchów

) składa się z cykli i łańcuchów

rozłącznych krawędzi. Jeśli łańcuch

rozłącznych krawędzi. Jeśli łańcuch

zawiera tylko jedną krawędź, jest to

zawiera tylko jedną krawędź, jest to

prosta; w przeciwnym razie jego dwie

prosta; w przeciwnym razie jego dwie

krawędzie skrajne są półprostymi.

krawędzie skrajne są półprostymi.



Jeśli S

Jeśli S

1

1

i S

i S

2

2

są oddzielone liniowo, to

są oddzielone liniowo, to

ζ

ζ

(S

(S

1

1

, S

, S

2

2

) składa się z pojedynczego

) składa się z pojedynczego

łańcucha monotonicznego.

łańcucha monotonicznego.

Dlaczego ma to w ogóle

Dlaczego ma to w ogóle

działać?

działać?



Niech

Niech

ζ

ζ

(S

(S

1

1

, S

, S

2

2

) dzieli płaszczyznę

) dzieli płaszczyznę

na część lewą (

na część lewą (

π

π

l

l

) i prawą (

) i prawą (

π

π

r

r

).

).



Jeśli S

Jeśli S

1

1

i S

i S

2

2

są rozdzielone liniowo

są rozdzielone liniowo

pionową prostą tak, że S

pionową prostą tak, że S

1

1

jest na

jest na

lewo od S

lewo od S

2

2

, diargam Voronoi Vor(S)

, diargam Voronoi Vor(S)

jest sumą części wspólnych Vor(S

jest sumą części wspólnych Vor(S

1

1

)

)

i

i

π

π

l

l

oraz Vor(S

oraz Vor(S

2

2

) i

) i

π

π

r

r

.

.

Algorytm właściwy

Algorytm właściwy



Dzielimy S na dwa podzbiory, S

Dzielimy S na dwa podzbiory, S

1

1

i S

i S

2

2

, o

, o

mniej więcej równej wielkości,

mniej więcej równej wielkości,

korzystając z mediany współrzędnych x.

korzystając z mediany współrzędnych x.



Tworzymy rekurencyjnie Vor(S

Tworzymy rekurencyjnie Vor(S

1

1

) oraz

) oraz

Vor(S

Vor(S

2

2

)

)



Tworzymy łańcuch

Tworzymy łańcuch

ζ

ζ

(S

(S

1

1

, S

, S

2

2

).

).



Odrzucamy wszystkie krawędzie Vor(S

Odrzucamy wszystkie krawędzie Vor(S

2

2

)

)

leżące na lewo od

leżące na lewo od

ζ

ζ

i wszystkie krawędzie

i wszystkie krawędzie

z Vor(S

z Vor(S

1

1

) leżące na prawo od

) leżące na prawo od

ζ

ζ

.

.

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Dla wzrokowców

Tworzenie łańcucha

Tworzenie łańcucha

dzielącego

dzielącego



Krok I: Znalezienie półprostych.

Krok I: Znalezienie półprostych.



Każda z półprostych dzieli

Każda z półprostych dzieli

prostopadle na pół odcinki

prostopadle na pół odcinki

wspierające Conv(S

wspierające Conv(S

1

1

) i Conv(S

) i Conv(S

2

2

).

).



Marsz od jednej półprostej do

Marsz od jednej półprostej do

drugiej.

drugiej.



Poszczególne "odcinki" łańcucha

Poszczególne "odcinki" łańcucha

zaczynają się i kończą na

zaczynają się i kończą na

krawędziach Vor(S

krawędziach Vor(S

1

1

) i Vor(S

) i Vor(S

2

2

) patrz

) patrz

twierdzenie 1.

twierdzenie 1.

Tworzenie łańcucha

Tworzenie łańcucha

dzielącego

dzielącego



Niech będzie dana krawędź e

Niech będzie dana krawędź e

(należący do

(należący do

ζ

ζ

) i bieżący węzeł v.

) i bieżący węzeł v.

Znaleźć następną krawędź e' oraz

Znaleźć następną krawędź e' oraz

węzeł v'.

węzeł v'.



Niech e rozdziela V(i) oraz V(j) dla p

Niech e rozdziela V(i) oraz V(j) dla p

i

i

należącego do S

należącego do S

1

1

oraz p

oraz p

j

j

należącego

należącego

do S

do S

2

2

.

.



Jak przeglądać brzegi Vor(S

Jak przeglądać brzegi Vor(S

1

1

) i

) i

Vor(S

Vor(S

2

2

)?

)?

Tworzenie łańcucha

Tworzenie łańcucha

dzielącego

dzielącego



Niech e

Niech e

1

1

, e

, e

2

2

, ..., e

, ..., e

k

k

należy do

należy do

ζ

ζ

i V(i).

i V(i).

Niech (b.s.o.) p

Niech (b.s.o.) p

i

i

należy do S

należy do S

1

1

.

.



Niech q

Niech q

1

1

, q

, q

2

2

, ..., q

, ..., q

k

k

będą przecięciami

będą przecięciami

między przedłużeniami krawędzi e

między przedłużeniami krawędzi e

1

1

,

,

e

e

2

2

, ..., e

, ..., e

k

k

, a brzegiem V(i) z Vor(S

, a brzegiem V(i) z Vor(S

1

1

).

).



Obserwacja: q

Obserwacja: q

1

1

, q

, q

2

2

, ... q

, ... q

k

k

jest

jest

uporządkowane na brzegu V(i)

uporządkowane na brzegu V(i)

zgodnie z ruchem wskazówek zegara.

zgodnie z ruchem wskazówek zegara.

Złożoność asymptotyczna

Złożoność asymptotyczna



T(N)=2T(N/2)+O(N)

T(N)=2T(N/2)+O(N)



Z twierdzenia o rekurencji

Z twierdzenia o rekurencji

uniwersalnej:

uniwersalnej:



N

N

log

log

2

2

2

2

=N zatem N

=N zatem N

log

log

2

2

2

2

=O(N)

=O(N)



T(N)=O(N lg N)

T(N)=O(N lg N)



Jest to czas optymalny.

Jest to czas optymalny.



Czy powinien nas ten wynik

Czy powinien nas ten wynik

zdziwić?

zdziwić?

Geometria

Geometria

Obliczeniowa

Obliczeniowa

Część V: Rozwiązywanie

Część V: Rozwiązywanie

problemów sąsiedztwa

problemów sąsiedztwa

diagramem Voronoi

diagramem Voronoi

Wszyscy najbliżsi sąsiedzi

Wszyscy najbliżsi sąsiedzi



Problem ten można w czasie

Problem ten można w czasie

liniowym przekształcić w Diagram

liniowym przekształcić w Diagram

Voronoi, co oznacza możliwość

Voronoi, co oznacza możliwość

rozwiązania go w czasie O(N lg N),

rozwiązania go w czasie O(N lg N),

który to czas jest optymalny.

który to czas jest optymalny.



Twierdzenie 3.

Twierdzenie 3.

Najbliższa para

Najbliższa para



Problem najbliższej pary można

Problem najbliższej pary można

przekształcić w czasie liniowym w

przekształcić w czasie liniowym w

problem wszystkich najbliższych

problem wszystkich najbliższych

sąsiadów, a zatem można go

sąsiadów, a zatem można go

rozwiązać dzięki diagramowi

rozwiązać dzięki diagramowi

Voronoi w czasie O(N lg N). Jest to

Voronoi w czasie O(N lg N). Jest to

czas optymalny.

czas optymalny.

Szukanie sąsiada

Szukanie sąsiada



Poszukiwanie najbliższego sąsiada

Poszukiwanie najbliższego sąsiada

może być wykonane w czasie O(lg

może być wykonane w czasie O(lg

N) przy użyciu pamięci O(N) i z

N) przy użyciu pamięci O(N) i z

czasem przetwarzania wstępnego

czasem przetwarzania wstępnego

O(N lg N), co stanowi rozwiązanie

O(N lg N), co stanowi rozwiązanie

optymalne.

optymalne.

Metody przeszukiwania PGP: metoda warstw, metoda łańcuchowa,

Metody przeszukiwania PGP: metoda warstw, metoda łańcuchowa,

(1977) metoda separatora na płaszczyźnie, metoda doskonalenia

(1977) metoda separatora na płaszczyźnie, metoda doskonalenia

triangulacji, metoda łańcuchowa z mostkowaniem i metoda trapezów

triangulacji, metoda łańcuchowa z mostkowaniem i metoda trapezów

Triangulacja (Delaunay)

Triangulacja (Delaunay)



Triangulacja charakteryzująca się

Triangulacja charakteryzująca się

tym, że okrąg na poszczególnych

tym, że okrąg na poszczególnych

trójkątach jest pusty (twierdzenie 2

trójkątach jest pusty (twierdzenie 2

i 4), może być znaleziona w czasie

i 4), może być znaleziona w czasie

O(N lg N) – jest to czas optymalny

O(N lg N) – jest to czas optymalny

dla dowolnej triangulacji.

dla dowolnej triangulacji.



EMST może być wyznaczone z

EMST może być wyznaczone z

triangulacji Delaunay.

triangulacji Delaunay.

Wypukła otoczka

Wypukła otoczka



Jeśli dany jest diagram Voronoi N

Jeśli dany jest diagram Voronoi N

punktów na płaszczyźnie, otoczka

punktów na płaszczyźnie, otoczka

wypukła może zostać znaleziona w

wypukła może zostać znaleziona w

czasie liniowym.

czasie liniowym.

To jeszcze nie koniec!!!

To jeszcze nie koniec!!!



Istnieje jeszcze bardzo wiele

Istnieje jeszcze bardzo wiele

problemów, które można rozwiązać za

problemów, które można rozwiązać za

pomocą Diagramu Voronoi

pomocą Diagramu Voronoi



Diagram Voronoi posiada jeszcze bardzo

Diagram Voronoi posiada jeszcze bardzo

wiele zaskakujących własności

wiele zaskakujących własności



Istnieją diagramy Voronoi w wyższych

Istnieją diagramy Voronoi w wyższych

wymiarach i wyższych rzędów

wymiarach i wyższych rzędów

CDN.

CDN.

Źródła

Źródła



Franco P. Preparata i Micheal Ian

Franco P. Preparata i Micheal Ian

Shamos.

Shamos.

Geometria obliczeniowa.

Geometria obliczeniowa.

Wprowadzenie.

Wprowadzenie.

Helion 2003.

Helion 2003.