Literature:
[1] Mark de Berg, Otfried Cheong (Schwarzkopf), Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications (look here)
[2] Note of György Elekes: pdf
[3] Luis Barba, Bernd Gärtner, Michael Hoffmann, Emo Welzl: Geometry: Combinatorics & Algorithms Lecture Notes: pdf
[4] Philipp Kindermann: Computational Geometry: recordings (slides)
See also:
Homepages of Géza Tóth, Dömötör Pálvölgyi, Jonathan Shewchuk, Dave Mount
Brief summary:
1.
- convex hull definitions, properties ([2] 3.1), computing the convex hull:
- gift wrapping algorithm ([2] 3.3.1, https://en.wikipedia.org/wiki/Gift_wrapping_algorithm)
- adding points from left to right, divide et impera ([1] 1., [2] 3.3.2)
- Chan's output sensitive algorithm (https://en.wikipedia.org/wiki/Chan's_algorithm)
2.
- computing the convex hull - lower bounds ([2] 3.5)
- computing the intersection of segments ([1] 2.1)
- the doubly-connected edge list ([1] 2.2)
3.
- computing the overlay of two subdivisions ([1] 2.3, 2.4)
- art gallery problem ([1] 3.1)
- partitioning a polygon into monotone pieces ([1] 3.2)
- triangulating a monotone polygon ([1] 3.3)
4.
- point location problem ([4] 06)
5.
- casting, manufacturing with molds ([1] 4.1)
- computing the intersection of half-planes ([1] 4.2)
- linear programming in the plane ([1] 4.3, 4.4, 4.5)
6.
- voronoi diagram - definition, properties, application (post office problem) ([1] 7.1)
- voronoi diagram - computation ([1] 7.2)
7.
- computing the smallest disk covering a point set ([1] 4.7)
- computing the smallest-width annulus covering a point set; the farthest point voronoi diagram ([1] 7.4)
8.
- ray tracing ([1] 8.0)
- duality ([1] 8.2, [2] 2)
- subdivision induced by straight lines in time O(n^2) ([1] 8.3, [2] 1.2)
- computing the discrepancy ([1] 8.1,8.4)
- bonus: discrepancy of hypergraphs with low maximum degree: the Beck-Fiala theorem (proof)
9.
- terrain approximation using legal triangulations ([1] 9.1)
- definition and properties of the Delaunay triangulation ([1] 9.2)
10.
- computing the Delaunay triangulation and the analysis of the algorithm ([1] 9.3, 9.4)
[1] könyv: Mark de Berg, Otfried Cheong (Schwarzkopf), Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications
[2] Elekes György jegyzete: pdf
[3] Luis Barba, Bernd Gärtner, Michael Hoffmann, Emo Welzl: Geometry: Combinatorics & Algorithms Lecture Notes: pdf
[4] Philipp Kindermann: Computational Geometry: videók (prezentációk)
[5] Jonathan Shewchuk honlapja
Lásd még: Pálvölgyi Dömötör és Tóth Géza honlapja
Vizsgatételek: pdf
Órák rövid összefoglalója:
1.
- konvex burok definíciók, tulajdonságok ([2] 3.1), konvex burok algoritmusok:
- Jarvis csomagkötöző avagy gift wrapping algoritmusa ([2] 3.3.1, https://en.wikipedia.org/wiki/Gift_wrapping_algorithm)
- balról jobbra pontok hozzávétele, divide et impera ([1] 1., [2] 3.3.2)
- Chan output szenzitív algoritmusa (https://en.wikipedia.org/wiki/Chan's_algorithm)
2.
- konvex burok alsó korlátok ([2] 3.5)
- szakaszok metszéspontjai ([1] 2.1)
- a duplán láncolt éllista ([1] 2.2)
3.
- két síkdarabolás összefésülése ([1] 2.3, 2.4)
- art gallery probléma ([1] 3.1)
- poligon háromszögelése: darabolás monoton részekre ([1] 3.2), monoton poligon háromszögelése ([1] 3.3)
4.
- pont helyzetének meghatározása ([2] 1.1)
5.
- öntés 3 dimenzióban ([1] 4.1)
- félsikok metszetének meghatározása nlog n időben ([1] 4.2)
- félsikok metszetének ürességének tesztelése n random várható időben - lineáris programozás a síkban ([1] 4.3, 4.4, 4.5)
6.
- voronoi diagram - definíció, tulajdonságok, alkalmazás (posta probléma) ([4] 07, [1] 7.1)
- voronoi diagram kiszámítása nlogn időben (Fortune algoritmusa) ([4] 07, [1] 7.2)
7.
- legvékonyabb tartalmazó gyűrű meghatározása, "farthest point" voronoi diagram - definíció, meghatározása nlog n random várható időben ([1] 7.4)
8.
- sugárkövetés ([1] 8.0)
- dualitás ([1] 8.2, [2] 2)
- egyenesekkel való darabolás meghatározása n^2 időben ([1] 8.3, [2] 1.2)
- diszkrepancia számítása ([1] 8.1,8.4)
- minimális tartalmazó kör meghatározása ([1] 4.7)
9.
- domborzat approximáció megengedett háromszögelésekkel ([1] 9.1)
- Delaunay-háromszögelés - definíció, tulajdonságok ([1] 9.2)
10.
- Delaunay-háromszögelés meghatározása nlogn random várható időben ([1] 9.3,9.4)
11.
- konvex burok 3 dimenzióban és alkalmazásai ([1] 11.2, 11.3, [4] 09, algoritmus analízis vége)
12.
- pont helyzetének meghatározása ismét ([4] 06)
[1] könyv: Mark de Berg, Otfried Cheong (Schwarzkopf), Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications
[2] Elekes György jegyzete: pdf
[3] Luis Barba, Bernd Gärtner, Michael Hoffmann, Emo Welzl: Geometry: Combinatorics & Algorithms Lecture Notes: pdf
[4] Philipp Kindermann: Computational Geometry, lecture videos: channel
Lásd még: Pálvölgyi Dömötör és Tóth Géza honlapja
Vizsgatételek: pdf
Órák rövid összefoglalója:
1.
- konvex burok definíciók, tulajdonságok ([2] 3.1), konvex burok algoritmusok:
- Jarvis csomagkötöző avagy gift wrapping algoritmusa ([2] 3.3.1, https://en.wikipedia.org/wiki/Gift_wrapping_algorithm)
- balról jobbra pontok hozzávétele, divide et impera ([1] 1., [2] 3.3.2)
- Chan output szenzitív algoritmusa (https://en.wikipedia.org/wiki/Chan's_algorithm)
2.
- konvex burok alsó korlátok ([2] 3.5)
- szakaszok metszéspontjai ([1] 2.1)
- a duplán láncolt éllista ([1] 2.2)
3.
- két síkdarabolás összefésülése ([1] 2.3, 2.4)
- art gallery probléma ([1] 3.1)
- poligon háromszögelése: darabolás monoton részekre ([1] 3.2), monoton poligon háromszögelése ([1] 3.3)
4.
- pont helyzetének meghatározása ([2] 1.1 vagy [4] 06)
5.
- öntés 3 dimenzióban ([1] 4.1)
- félsikok metszetének meghatározása nlog n időben ([4] 04)
- félsikok metszetének ürességének tesztelése n random várható időben - lineáris programozás a síkban ([4] 04)
6.
- voronoi diagram - definíció, tulajdonságok, alkalmazás (posta probléma) ([4] 07, [1] 7.1)
- voronoi diagram kiszámítása nlogn időben (Fortune algoritmusa) ([4] 07, [1] 7.2)
7.
- minimális tartalmazó kör meghatározása ([1] 4.7)
- legvékonyabb tartalmazó gyűrű meghatározása, "farthest point" voronoi diagram - definíció, meghatározása nlog n random várható időben ([1] 7.4)
8.
- sugárkövetés ([1] 8.0)
- egyenesekkel való darabolás meghatározása n^2 időben ([1] 8.3, [2] 1.2)
- dualitás ([1] 8.2, [2] 2)
- diszkrepancia számítása ([1] 8.1,8.4)
9.
- domborzat approximáció megengedett háromszögelésekkel ([4] 08)
- Delaunay-háromszögelés - definíció, tulajdonságok ([4] 08)
10.
- Delaunay-háromszögelés meghatározása nlogn random várható időben ([1] 9.3,9.4)
11.
- mozgástervezés avagy motion planning ([4] 06)
12.
- konvex burok 3 dimenzióban és alkalmazásai ([4] 09)
[1] könyv: Mark de Berg, Otfried Cheong (Schwarzkopf), Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications
[2] Elekes György jegyzete: pdf
[3] Luis Barba, Bernd Gärtner, Michael Hoffmann, Emo Welzl: Geometry: Combinatorics & Algorithms Lecture Notes: pdf
Lásd még: Pálvölgyi Dömötör és Tóth Géza honlapja
Vizsgatételek: pdf
Órák rövid összefoglalója:
1.
- konvex burok definíciók, tulajdonságok
- konvex burok algoritmusok
2.
- konvex burok alsó korlátok
- szakaszok metszéspontjai
- a duplán láncolt éllista
3.
- két síkdarabolás összefésülése
- art gallery probléma
- poligon háromszögelése
4.
- pont helyzetének meghatározása
5.
- öntés 3 dimenzióban; casting, manufacturing with molds ([1] 4.1)
- félsikok metszetének meghatározása nlog n időben; computing the intersection of half-planes ([1] 4.2)
- félsikok metszetének ürességének tesztelése n random várható időben - lineáris programozás korlátos és nem-korlátos eset, síkban részletesen, nagyobb dimenziós térben röviden; linear programming in the plane bounded and non-bounded case, in higher dimension briefly ([1] 4.3, 4.4, 4.5 and 4.6 very briefly; you can see also [3] appendix F)
- minimális tartalmazó kör meghatározása n random várható időben; computing the smallest enclosing disk ([1] 4.7)
6.
- voronoi diagram - definíció, tulajdonságok, alkalmazás (posta probléma); voronoi diagram - definition, properties, application (post office problem) ([1] 7.1)
- voronoi diagram kiszámítása nlogn időben (Fortune algoritmusa); computation of the voronoi diagram (Fortune's algorithm) ([1] 7.2)
7.
- szakaszok voronoi diagramja, alkalmazás (motion planning); voronoi diagram of line segments, application to motion planning ([1] 7.3)
- legvékonyabb tartalmazó gyűrű meghatározása n^2 időben, "farthest point" voronoi diagram - definíció, meghatározása nlog n random várható időben; computing the smallest-width annulus covering a point set; the farthest point voronoi diagram - definition, computation ([1] 7.4)
8.
- sugárkövetés; ray tracing ([1] 8.0)
- egyenesekkel való darabolás meghatározása n^2 időben; computing the subdivision induced by straight lines ([1] 8.3 or [2] 1.2)
- dualitás; duality ([1] 8.2 or [2] 2)
- diszkrepancia számítása; computing the discrepancy ([1] 8.1,8.4)
9.
- domborzat approximáció megengedett háromszögelésekkel; terrain approximation using legal triangulations ([1] 9.1)
- Delaunay-háromszögelés - definíció, tulajdonságok; definition and properties of the Delaunay triangulation ([1] 9.2)
- Delaunay-háromszögelés meghatározása nlogn random várható időben; computing the Delaunay triangulation and the analysis of the algorithm ([1] 9.3,9.4)
[1] Book: Mark de Berg, Otfried Cheong (Schwarzkopf), Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications
[2] Note of György Elekes: pdf
See also: homepages of Dömötör Pálvölgyi and Géza Tóth
Exam topics: pdf
Brief summary:
1.
- computing the convex hull:
- gift wrapping algorithm ([2] 3.3.1, https://en.wikipedia.org/wiki/Gift_wrapping_algorithm)
- adding points from left to right, divide et impera ([1] 1., [2] 3.3.2)
- Chan's output sensitive algorithm (https://en.wikipedia.org/wiki/Chan's_algorithm)
2.
- computing the convex hull - lower bounds ([2] 3.5)
- computing the intersection of segments ([1] 2.1)
- the doubly-connected edge list ([1] 2.2)
3.
- computing the overlay of two subdivisions ([1] 2.3, 2.4)
- art gallery problem ([1] 3.1)
- partitioning a polygon into monotone pieces ([1] 3.2)
4.
- triangulating a monotone polygon ([1] 3.3)
- point location problem ([2] 1.1)
5.
- computing the subdivision induced by straight lines ([2] 1.2 or [1] 8.3)
- casting, manufacturing with molds ([1] 4.1)
- computing the intersection of half-planes ([1] 4.2)
- linear programming in the plane ([1] 4.3, 4.4, 4.5 and 4.6 very briefly)
6.
- voronoi diagram - definition, properties, application (post office problem) ([1] 7.1)
- fire alarm
7.
- voronoi diagram - computation ([1] 7.2)
- voronoi diagram of line segments (briefly), application to motion planning ([1] 7.3)
8.
- computing the smallest-width annulus covering a point set; the farthest point voronoi diagram ([1] 7.4)
- computing the smallest disk covering a point set ([1] 4.7)
9.
- ray tracing
- computing the discrepancy using duality and the subdivision induced by straight lines (see lecture 5) ([1] 8.1,8.2,8.4)
- terrain approximation using legal triangulations ([1] 9.1)
10.
- definition and properties of the Delaunay triangulation ([1] 9.2)
- computing the Delaunay triangulation and the analysis of the algorithm except the bound on sum(card(K(Delta))) ([1] 9.3 and 9.4 except Lemma 9.13)
11.
- bound on sum(card(K(Delta))) in the analysis of the Delaunay triangulation algorithm ([1] Lemma 9.13)
- computing a minimal length spanning tree of a point set ([1] 9.7 Excercises 9.11 and 9.12)
- 3d convex hull algorithm in exp. O(nlogn) time ([1] 11.1,11.2, Lemma 11.3, Lemma 11.4)
12.
- missing part of 3d convex hull algorithm analysis: bound on sum(card(P(e)))(in [1] 11.3 there is a proof based on [1] 9.5, during class a less general simpler proof was presented similar to Lemma 9.13)
- gift wrapping algorithm for 3d convex hull
- Chan's output sensitive algorithm for 3d convex hull
- basic statements about n dimensional convex hull algorithms ([1] 11.6)
- convex hulls and half-space intersection ([1] 11.4)
- voronoi diagrams and upper envelopes of planes ([1] 11.5)