Toepassingen van Meetkunde in de Informatica

Ga naar: navigatie, zoeken
DirkRoose.jpg


Inhoud

Samenvattingen

Klik hier om de samenvattingen te bekijken

Samenvatting TMI door Jonas Soenen: Deel 1 Deel 2

Vakevaluatie

Elk puntje hieronder is iemands mening. Verander aub geen puntjes. Als je een andere mening hebt, gelieve ze onderaan toe te voegen.

Kwaliteit cursus (prijs, duidelijkheid, overeenkomst met les, ...)

  • 2017: De cursusnota's van Prof. Dirk Roose zijn beknopt. Voor het tweede deel is het de bedoeling dat je leert uit kopieen van andere handboeken.

Studiebelasting (aantal studiepunten in verhouding met bestede tijd)

  • 2017: Normaal voor 6 sp. Wekelijks een college en een oefenzitting. Er is een practicum waarvoor je meer dan een half semester de tijd krijgt. Als je daar vroeg aan begint, is dat zeker te doen. Sommigen hebben iets meer tijd nogdig om het algoritme te bedenken en zonder fouten te implementeren. Tijdens de blok ben je vooral bezig met het studeren van bewijzen.

Plaats binnen de opleiding (nodige voorkennis, overlap met andere vakken, relevantie van het vak,...)

  • 2017: Deel 1 overlapt eigenlijk niet met andere vakken, maar het is wel een inleiding tot computergrafiek, voor als je dat in de master volgt. Deel 2 is eerder een vervolg op G&A.

Manier van lesgeven bij hoorcolleges (snelheid, verstaanbaarheid, structuur, nut, ...)

  • 2017: De colleges zijn niet slecht.

Evaluatie oefenzittingen/labo's (nut, begeleiding, ...)

  • 2017: Assistent Nico Scheerlinck geeft echt les, waardoor je alles aan het einde van de oefenzittingen veel beter begrijpt. Zeker aangeraden, dus, ook al is het examen eerder theorie.

Examen (mate waarin het een weerspiegeling is van de cursus, examenvorm, ...)

  • 2017: Een aantal theorievragen (bespreek en bewijs de correctheid van geziene algoritmen), die voornamelijk over deel 2 gaan. Je moet ook zelf een algoritme bedenken gebaseerd op de cursus. De punten worden niet per vraag toegekend, maar Prof. Roose geeft een "globale kwotering" over het examen en practicum samen. Hij heeft uitspraken gedaan als "Waarom moeten we punten linair optellen en niet vermenigvuldigen? Als je op een vraag een nul hebt, dan ken je het vak eigenlijk niet".

Examen

Informatie

Het examen is gesloten boek, behalve het deel over padplanning. Je mag dus Hoofdstuk 8 van O'Rourke gebruiken op het examen. Deze bladzijden mogen enkel informatie over padplanning bevatten, er mag dus niet op de achterkant informatie over iets anders op neergepend staan. Roose komt PERSOONLIJK langs iedere student om tussen je papieren te bladeren, neem dus geen risico's... Je mag ook het formularium over Deel I. Curven en oppervlakken (zie achteraan de Nederlandstalige cursusnota's) gebruiken op het examen. Dit moet je zelf meenemen, het wordt niet uitgedeeld op het examen.

denk ook nooit dat iets te simpel is, om gevraagd te worden:
Roose durft ALLES te vragen

Roose is gesteld op ordelijkheid. Lelijk geschrift, doorgeschrapte zaken of onnauwkeurigheden kunnen hem irriteren. Vergeet geen potlood en lat mee te nemen om zaken te kunnen verduidelijken. Een passer is ook wel handig voor de oefeningen over robotarmen (komt vaak voor).

Roose is vriendelijk en efficiënt als je je mondelinge verdediging doet. Hij kan er wel absoluut niet tegen dat je een vraag blanco laat, schrijf dus gewoon alles op wat je weet (maar draai niet rond de pot, hij doorprikt een blad vol holle woorden onmiddelijk.)

Academiejaar 2014-2015

In academiejaar 2014-2015 werd het deel over robotarmen (deel 2 van hoofdstuk 8 in O'Rourke) niet meer gezien. In de plaats ervan kwam een stuk over het vinden van oppervlakken en curven in puntwolken.

Academiejaar 2015-2016

In academiejaar 2015-2016 werden in de laatste les (na het algoritme van Fortune, einde van de cursustekst) het museumprobleem en motion planning besproken. Robotarmen kwamen niet aan bod.

Academiejaar 2016-2017

De laatste lessen gingen over padplanning van robots, het museumbewakersprobleem en puntenwolken.

Theorie

Bézier curven

  • Bespreek continuiteit.
  • hoe bekomt men continuiteit bij samengestelde bézier curven
  • geef het algoritme van de Casteljau
  • variatieverminderingseigenschap algemeen + wat betekent ze specifiek voor béziercurven
  • bespreek subdivisie + methode
  • bespreek graadverhoging + bewijs formule + nut
  • waarom gebruikt men samengestelde béziercurven + wat voor problemen treden erbij op?
  • bespreek constructie van samengestelde béziercurven + voor/nadelen
  • tensor-product Bezier-veeltermen hoe?
  • Afgeleide Dxy(x0,y0) in hoekpunten parameteropp. afleiden + grafisch weergeven.
  • bespreek de constructie van tensor bezier product en leidt D(uv) af + grafische interpretatie

B-spline curven

  • bewijs dat de sommatie tot een eigenschap geldt voor de genormaliseerde B-splines dwz voor
  • hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? hoeveel moeten er samenvallen?
  • Hoe kan men bij splines punten laten interpoleren door het samennemen van knooppunten?
  • variatieverminderingseigenschap algemeen + wat betekent ze specifiek voor splines
  • algoritme van de boor + nauwkeurige tekening en bewijs van correctheid
  • hoe kan je ervoor zorgen dat een deel van een spline curve een recht lijnstuk is? waarom?
  • hoe spline interpoleren met meervoudige knooppunten.

Algemeen

  • Wat is bounding box quick rejection test uit algo om te bepalen of 2 rechten elkaar snijden. Geef de 2 toepassingen in het algo + implementatie
  • bespreek het algoritme voor het bepalen van de onderbrug en bovenbrug waarom is de kleinste y-coordinaat een slechte schatting voor het bepalen van de onderbrug?
  • geef een algoritme dat in O(N log N) bewerkingen nagaat of in een vz van N lijnstukken er snijdende lijnstukken in voorkomen

Bewijs correctheid van dit algoritme geef beknopt hoe dit algoritme en de gegevensstrukturen moeten aangepast worden om alle snijdingen te vinden

  • geef een algoritme voor de berekening van het VPP van een vz van N punten in O(nlog n) bewerkingen

verantwoord de rekencomplexiteit

  • bespreek graham scan + correctheidsbewijs + toon aan dat dit O(nlogn)bewerkingen gebeurt
  • wanneer is de inpakmethode (jarvis march) efficienter dan de methode van graham (graham scan)

Voronoi diagrammen

  • bewijs: een voronoi diagramma van een vz S heft maximaal 2N - 5 voronoipunten en 3N - 6 voronoi zijden
  • een voronoiveelhoek van een punt pi is begrensd <=> pi element van inw(CH(S)) + nut + waar hebben we dit gebruikt?
  • bewijs dat minimale doorloopboom deelverzameling is van de Delaunay triangulatie. wat is het nut van deze eigenschap?
  • 2 dichtste buren hebben een gemeenschappelijke voronoizijde: bewijs
  • geef strategie + hoog-niveau algoritme voor het vinden van de maximale lege cirkel binnen de COV van een verzameling punten.
  • p(i) behoort tot de inwendige van V(i) asa V(i) is begrensd

Nabijheidsproblemen

  • wat betekent volgende uitspraak: probleem A is ?(N) transformeerbaar tot probleem B? waarvoor kan een dergelijke uitspraak nuttig gebruikt worden + vb
  • wat is een EMDB van een vz punten + verband met Voronoi diagramma van een vz punten?
  • bespreek beknopt hoe een EMDB van een vz punten kan berkend worden in O(nlogn) bewerkingen

Fortune

  • bespreek de overganspunten bij fortune-algoritme
  • Bespreek de events in het algoritme van Fortune Welke acties moeten ondernomen worden?

Andere

De leerstof na Fortune verandert van jaar tot jaar, niet schrikken dus als hier iets compleet onbekends bij staat.

  • Hoe bepaal je het gebied dat kan bereikt worden door een robotarm met 3 links. Is de volgorde van de stukken belangrijk?
  • Minkovski-som gebruiken en zeggen welke het is
  • Bewijs dat floor(n/3) bewakers altijd genoeg zijn om een veelhoekige plattegrond te bewaken.

Oefeningen

vraag1

Gegeven een 3 link probleem L1 = 150 L2 = 75 L3 = 40 Los op voor een punt P dat op 180 cm van de schouder ligt.

vraag2

Maak een hoog-niveau algoritme voor alle snijdingen van een verzameling cirkels.

vraag3

een minkowski-som tekenen

vraag4

gegeven punten op cirkel. Vind de driehoek met het grootste oppervlak.
(opl mbv tegenvoetparen)

vraag5

bespreek of 2 eenvoudige veelhoeken geheel of gedeeltelijk overlappen (uitleg + hoog niveau algo)
in O((N + M) log (N + M)) bewerkingen

vraag6

1 punt gegeven en allemaal lijnstukken (niet snijdende) rond dat punt
schrijf algo om te controleren of je een rechte kunt tekenen vanuit het gegeven punt tot al die rechten
(maw: welke rechten zijn zichtbaar voor dat punt)

vraag7

gegeven een eenvoudige veelhoek
bepaal of pi, pi+2 een diagonaal is van die veelhoek in O(n)

vraag8

n cirkels, elk bepaald door middelpunt pi en straal ri
bedenk een strategie om na te gaan of er cirkels snijden + algo

vraag9

algoritme om na te gaan of pi,pi+1 diagonaal in eenvoudige veelhoek
is in O(n)
Klopt dit wel: een diagonaal is een lijnsegment tussen twee vertices (hoekpunten) die niet aangrenzend zijn, terwijl pi en pi+1 wel aangrenzend zijn. (Klopt inderdaad niet. Wellicht dezelfde vraag als (7))

vraag10

Gegeven, p cirkels die elkaar niet overlappen, met gegeven middelpunten m en stralen r.
Ook gegeven: n punten p. Elk punt ligt in 1 cirkel.
Bedenk een algoritme dat in O((n + p)*lg(n + p)) kan bepalen welke punten in welke cirkels liggen.
Je moet geen rekening houden met randgevallen, om het algoritme iets simpeler te houden.
Tip: bv doorlooplijnalgoritme

Recente examens

27/06/2018 Voormiddag

    • Rationale Beziercurven: bespreek. Vergelijk met gewone Beziercurven. Geef een voorbeeld van een curve die wel met rationale Beziercurven voorgesteld kan worden, en niet met gewone Beziercurven.
    • Hoe kunnen we Bspline curven laten interpoleren door samenvallende controlepunten. Hoeveel van deze controlepunten moeten samenvallen. Verklaar duidelijk waarom.
  1. Bewijs dat een Voronoidiagram met N sites maximaal 2N-5 Voronoipunten en 3N-6 Voronoizijden kan hebben. Wat is een gevolg van feit dat het aantal zijden altijd O(N) is?
  2. Leg uit hoe een octree-datastructuur gebruikt kan worden voor efficiente operaties op een puntenwolk.
  3. Als A t(N) transformeerbaar is tot B, wat kunnen we hieruit besluiten?
  4. Algoritme ontwerpen met een complexiteit van O(N*logN): bepalen of er snijding is tussen een aantal rechthoeken.
  5. Bespreking verslag.

26/06/2018 Voormiddag

    • Variatieverminderingseigenschap in verband met Bezier curven
    • Toon met een teken de werking van de algoritme van de Boor (graad n = 3) en bewijs.
  1. Welke gegevensstructuren worden er gebruikt voor Voronoidiagramma. Welke bewerkingen kan je daarop doen (hoe bepaal je welke site in welke vlak zit en zo, hoe bepaal je een vlak met u zijden,...)
  2. Museumbewakersprobleem: bewijs dat floor(n/3) genoeg is om een eenvoudige veelhoek te bewaken.
  3. Gegeven zijn een paar cirkels: zoek een algoritme (liefst in O(n log n)) die bepaalt of er een snijding is. (Los op door een sweepline, sorteer op x_min en x_max van de cirkels en binnen die lus sorteer kan je kijken of y_max < y_min van de vorige cirkel: want dan is er geen snijding)
  4. Bespreek verslag

19/06/2018 Namiddag

    • Variatieverminderingseigenschap in verband met Bezier curve
    • stel dat je een bezier oppervlak hebt met x(r,s). Stel dat r een constante is, toon aan dat dit dan een beziercurve is en geef de controlepunten van deze curve.
  1. Hoogniveau algoritme voor bepalen van onderbrug en leg de rekencomplexiteit uit
  2. Som van Minkowski met ster-diagramma uitvoeren
  3. Verzin zelf hoogniveau doorlooplijnalgoritme voor volgende probleem: gegeven een k punten en k rechthoeken die gegeven worden door het punt linksonder en rechtsboven van de rechthoek. Zoek een algoritme dat aangeeft welk punt bij welke rechthoek hoort.
  4. Bespreek verslag

19/06/2018 voormiddag

  1. Bespreek de voorwaarden voor C2-continuiteit bij samengestelde Béziercurven. Wat moeten we doen om C2-continuiteit te bekomen bij splinecurven? (= examen 9/6/2015, vraag 1)
  2. Het Voronoi-gebied van een punt p uit S is begrensd als en slechts als dat punt in het inwendige van S ligt. Waar hebben we deze eigenschap gebruikt? (1 voorbeeld is voldoende). Bewijs deze eigenschap. (= examen 9/6/2015, vraag 2)
  3. Antwoord beknopt: wanneer gebruikt men best de inpakmethode (Jarvis) in plaats van de Graham's scan? (Beknopt meent hij wel: 3-4 lijnen is genoeg, complexiteiten vergelijken.) (= examen 21/6/2016, vraag 3)
  4. Teken Minkowski som voor gegeven robot en veelhoek adhv ster-diagram.
  5. S is een verzameling van n lijnstukken die elkaar niet snijden en p is een willekeurig punt, dat niet op één van deze lijnstukken ligt (er is een tekeningetje bij met in het midden een punt p en daar rond een paar lijnstukken). Een lijnstuk is zichtbaar vanuit p indien het een punt q bevat zodat er geen lijnstukken tussen p en q liggen. Stel een algoritme op dat alle lijnstukken van S bepaalt (en afdrukt) die vanuit p zichtbaar zijn. Er bestaat een algoritme met rekencomplexiteit O(nlogn) dat gebruik maakt van een roterende halfrechte vanuit p. Leg eerst de algemene strategie uit, en geef dan een 'hoog niveau' pseudo-code beschrijving van het algoritme. Je hoeft geen rekening te houden met speciale gevallen. (= examen 27/6/2011, vraag 5)
  6. Bespreking practicum.

27/06/2017 Namiddag

  1. Bespreek opsplitsing en graadverhoging van Beziercurven
    1. Wat is het nut ervan?
    2. Illustreer met een voorbeeld
    3. Bewijs de formules (details zijn niet belangrijk, gewoon de structuur en de trucjes die je moet toepassen)
  2. Wat moet je doen bij de overgangspunten van het algoritme van Fortune? Beschrijf op zeer hoog niveau.
  3. Bespreek de Graham Scan: pseudocode, tijdscomplexiteit en correctheidsbewijs (opnieuw enkel de belangrijkste stappen)
  4. Teken de relevante Minkowski som voor een gegeven robot en obstakel.
  5. Schrijf een algoritme voor de triangulatie van een niet-convexe veelhoek. Het basisprincipe moet gaan als volgt: je wil van de veelhoek telkens een hoek afknippen. Die wordt bepaald door een diagonaal van een punt p_i naar p_{i+2}. Geef dus eerst een gedetailleerd algoritme om te bepalen of een lijnstuk p_i -> p_{i+2} een diagonaal is (de nummering van de punten is in tegenwijzerzin). Schrijf vervolgens een algoritme dat telkens een hoek afknipt en verdergaat met de rest van de veelhoek totdat deze volledig getrianguleerd is.
  6. Bespreking van het practicum over het vinden van alle snijpunten van een verzameling cirkels.

23/06/2016 Voormiddag

  1. Splines laten interpoleren door een bepaald punt met samenvallende controlepunten. Leg uit. Kan interpolatie ook op een andere manier bekomen worden?
    • Het Voronoi-gebied horende bij een punt i is begrensd <=> het punt binnen de convex omhullende veelhoek ligt van de puntenverzameling. Waar hebben we deze eigenschap gebruikt en bewijs.
    • Algoritme voor het bepalen van de onderbrug: werkt het algoritme voor elke beginschatting? (beknopt antwoorden)
  2. Celdecompositie bij padplanning bespreek
  3. algoritme om de triangulatie van een veelhoek te berekenen (wel heel wat info gekregen)
  4. Bespreek verslag

22/06/2016 Namiddag

    • Variatieverminderingseigenschap
    • Teken de werking van de Boor-algoritme voor B-spline met graad n = 3 & bewijs het de Boor-algoritme
  1. Hoogniveau algoritme voor bepalen van verste puntenparen en leg de rekencomplexiteit uit
  2. Som van Minkowski met ster-diagramma uitvoeren
  3. Verzin zelf hoogniveau doorlooplijnalgoritme voor het dichtste puntenpaar van N punten te bepalen en leg de rekencomplexiteit uit
  4. Bespreek verslag

21/06/2016 namiddag

    • Hoeveel controle punten moet je laten samenvallen om een spline curve te laten interpolleren in een punt, leg volledig uit
    • stel dat je een bezier oppervlak hebt met x(r,s). Stel dat r een constante is, toon aan dat dit dan een beziercurve is en geef de controle punten van deze curve. Bijvraag tijdens het mondeling "in welke punten interpoleert een bezieroppervlak ?"
  1. Toon aan dat de complexiteit van het algoritme van jarvis lineair afhankelijk is van het aantal hoekpunten
  2. Toon aan hoe men kan bewijzen dat floor(n/3) bewakers genoeg zijn om een (veelhoekige) plattegrond te bewaken.
  3. Geef een algoritme voor het bepalen van de E.M.D.B, op welke eigenschappen steunt dit algoritme ? Bewijs een van deze eigenschappen
  4. Gegeven een verzameling cirkels die elkaar niet snijden en een verzameling lijnstukken die elkaar ook niet snijden. Geef een algoritme dat alle cirkels als resultaat geeft die niet snijden met een lijnstuk. Wat is de complexiteit van je algoritme en denk je dat dit de minimale complexiteit is.
  5. bespreking practicum

21/06/2016 voormiddag

    • Wat is het nut van het de Casteljau-algoritme (voor Bézier-curven) en het de Boor-algoritme (voor splines)?
    • Bewijs de correctheid van het de Casteljau-algoritme en illustreer. (Als illustratie volstaat het gewoon om het algoritme meetkundig uit te voeren met verhoudingen en lijnstukken voor het construeren van x(t).)
  1. Doorlooplijnalgoritme voor Voronoi-diagramma: Welke overgangspunten worden er gebruikt, hoe worden ze bepaald en welke acties moeten uitgevoerd worden. (Volledige opsomming van stappen is gevraagd, maar beschrijf elke stap "summier".)
  2. Antwoord beknopt: wanneer gebruikt men best de inpakmethode (Jarvis) in plaats van de Graham's scan? (Beknopt meent hij wel: 3-4 lijnen is genoeg, complexiteiten vergelijken.)
  3. Bewijs beknopt dat floor(n/3) bewakers genoeg zijn om een (veelhoekige) plattegrond te bewaken.
  4. Gegeven een verzameling punten p_1, ..., p_n en cirkels c_1, ..., c_k (voorgesteld door middelpunten en stralen (niet zozeer gelijk)). De cirkels overlappen niet (ook niet gedeeltelijk) en elk punt ligt in een cirkel. Ontwerp een algoritme dat voor alle punten de corresponderende cirkel berekent met een complexiteit van O((n + k)*log(n + k)). Leg eerst je strategie uit en schrijf je algoritme dan uit in "hoog-niveau" pseudocode.
  5. Bespreking practicum.

20/06/2016 Voormiddag

    • Leg variatievermindering uit. Geef de eigenschap en bespreek. (Dus waarom het handig is die te gebruiken).
    • Bespreek een tensor Bézieroppervlaktesegment. Hoe bepaalt men die met een parameter P(u*,v*)?.
  1. Een verdeel en heers algoritme bepaald de convexe van een verzameling door deze op te splitsen in twee op x-waarden te sorteren, hier de convexe van te berekenen, en dan een onder en bovenbrug te bepalen.
    1. Hoe ziet het algoritme voor de onderbrug er uit?
    2. Wat is diens complexiteit?
    3. Is de keuze van het beginpunt van belang voor dit algoritme?
    4. Een Delaunay-triangulatie bepaalt de duale graaf van een Voronoi-diagramma. Leg uit.
    5. Waarom wordt dit gedaan?
  2. Een robot A beweegt rond een polygon P, illustreer de Minowki som en het sterdiagram. Bijvraag: Waarom gebruikt men het sterdiagram, als je P+ ook zonder deze kan tekenen.
  3. Een camera staat in een vlak waar niet-transparante lijnstukken zijn, deze camera kan 360° roteren. Bepaal nu voor elk volledig zichtbaar lijnstuk was zijn lengte is. Geef een algoritme dat dit probleem oplost in O(n log n). Geef eerst een beschrijving, en zet die om in pseudo-code.
  4. Bespreking van het verslag.

24/06/2015 namiddag

    • Leg de variatie-verminderingseigenschap bij Beziér-curven uit. Wat is het belang ervan bij het ontwerpen van curves?
    • Maak een kwalitatief correcte tekening (dus niet numeriek juist maar wel duidelijk genoeg om et algoritme te kunnen uitleggen) van het algoritme van de Boor en bewijs de correctheid ervan.
  1. Bespreek het algoritme voor het dichtste puntenpaar. Wat is de tijdscomplexiteit (geef voldoende uitleg). Geef een hoog-niveau beschrijving (geen gedetailleerd algoritme)
  2. Hoe berekent men de normaal van het lokaal oppervlak in punt in een puntenwolk?
  3. Ontwerp een doorlooplijnalgoritme dat het dichtste puntenpaar vindt. Er bestaat een algoritme dat in tijd O(n log(n)) loopt. Wat is de tijdscomplexiteit? Denk je dat er een algoritme bestaat dat sneller loopt? Waarom?
  4. Bespreking practicum

23/06/2015 voormiddag

  1. Hoe kan je een spline-curven laten interpoleren in een controlepunt. Hoeveel en welke controlepunten moeten samenvallen. Leg uit.
  2. Gegeven een Bezier-oppervlak s(r, u). Stel nu r = r_c een constante. Waarom is s(r_c,u) een Bezier-curve, wat zijn de controlepunten ervan.
  3. Geef het algoritme voor het bepalen van een EMDB. Op welke eigenschappen steunt dit algoritme. Bewijs een van deze eigenschappen.
  4. Leg beknopt uit hoe je kan bewijzen dan er maximaal floor(n/3) bewakers nodig zijn om een veelhoekig grondplan te laten bewaken.
  5. Gegeven een verzameling niet snijdende lijnstukken en een verzameling niet snijdende cirkels (cirkels kunnen in andere cirkels liggen, maar geen 2 twee cirkels hebben gemeenschappelijke punten). Geef een efficient algoritme om te bepalen welke cirkels niet door een lijnstuk gesneden worden. Wat is de complexiteit van je algoritme?
  6. Bespreking practicum.

9/06/2015 namiddag

  1. Bespreek de voorwaarden voor C2-continuiteit bij samengestelde Béziercurven. Wat moeten we doen om C2-continuiteit te bekomen bij splinecurven?
  2. Het Voronoi-gebied van een punt p uit S is begrensd als en slechts als dat punt in het inwendige van S ligt. Waar hebben we deze eigenschap gebruikt? (1 voorbeeld is voldoende). Bewijs deze eigenschap.
  3. Een verzameling niet snijdende lijnstukken in het vlak is gegeven. Op een punt p bevindt zich een robot die 360° kan roteren. Deze robot kan de lengte van een lijnstuk berekenen als beide uiteinden zichtbaar zijn voor de robot. Schrijf een algoritme dat dit doet voor alle lijnstukken waarvoor dit mogelijk is. Geef eerst een overzicht van de algemene strategie, en specifieer het vervolgens verder in een hoog-niveau beschrijving. Er bestaat een O(n log n) algoritme.
  4. Hoe kan een 'octree' gebruikt worden om bepaalde operaties in de context van puntenwolken efficienter te laten verlopen.
  5. Bespreking practicum.

10/06/2014 namiddag

  1. Bespreek C2-continuiteit bij samengestelde Béziercurven en splinecurven.
  2. Bespreek de overgangspunten bij een doorlooplijn algoritme voor een voronoi diagram te construeren. (Fortune) Zeg ook kort wat er gebeurt in die overgangspunten.
  3. Robot + obstakel gegeven. Teken de Minkowskisom.
  4. Tekening met punt P gegeven tenmidde een verzameling lijnstukken. Een camera op punt P kan 360° rondkijken. Deze camera kan de afstand van een lijnstuk berekenen als hij beide eindpunten van een lijnstuk kan zien. Geef een algoritme dat als uitvoer heeft alle lijnstukken waarvan de afstand berekend kan worden.
  5. Bespreking practicum.

27/06/2011 voormiddag

    • Wat betekent 'Het verband tussen een Béziercurve en zijn Bézierpunten is invariant onder een affiene transformatie.'?
    • Hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? Welke en hoeveel moeten er samenvallen? Leg duidelijk uit waarom.
    • Hoe bewijs je dat een Voronoi-diagram van een verzameling van N sites maximaal 2N-5 Voronoi-punten en maximaal 3N-6 Voronoi-zijden bezit?
    • Waarom is het belangrijk dat het aantal Voronoi-zijden O(N) is? Geef minstens één voorbeeld van het nut van deze eigenschap.
  1. Geef beknopt aan hoe je kan bewijzen dat |_ N/3 _| 'bewakers' (die 360° kunnen rondkijken) voldoende zijn om een veelhoekige plattegrond te 'bewaken'.
  2. Practicum bespreken
  3. S is een verzameling van n lijnstukken die elkaar niet snijden en p is een willekeurig punt, dat niet op één van deze lijnstukken ligt (er is een tekeningetje bij met in het midden een punt p en daar rond een paar lijnstukken). Een lijnstuk is zichtbaar vanuit p indien het een punt q bevat zodat er geen lijnstukken tussen p en q liggen. Stel een algoritme op dat alle lijnstukken van S bepaalt (en afdrukt) die vanuit p zichtbaar zijn. Er bestaat een algoritme met rekencomplexiteit O(nlogn) dat gebruik maakt van een roterende halfrechte vanuit p. Leg eerst de algemene strategie uit, en geef dan een 'hoog niveau' pseudo-code beschrijving van het algoritme. Je hoeft geen rekening te houden met speciale gevallen.

20/06/2011 voormiddag

    • Wat betekent 'Het verband tussen een Béziercurve en zijn Bézierpunten is invariant onder een affiene transformatie.'? (Hier bedoelt hij mee dat W(Bi) -> Bi' is voor alle controlepunten i. Gevolg: we kunnen een Béziercurve transformeren door enkel zijn controlepunten te transformeren in plaats van ieder punt van de curve te moeten transformeren.)
    • Hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? Welke en hoeveel moeten er samenvallen?
    • Hoe kan men bij splines punten laten interpoleren door het samennemen van knooppunten? Welke en hoeveel moeten er samenvallen?
  1. Geef het hoog-niveau algoritme om het verste puntenpaar in een verzameling van N punten te vinden, en leg uitvoerig de tussenstappen en hun tijdscomplexiteit uit (Gebruik een tekening om het zoeken naar tegenvoetersparen van een punt te verduidelijken.)
  2. robotarm: l1 = 30 cm, l2= 20 cm en l3 = 40 cm en het te bereiken punt op 45 cm van de schouder. Leg uit hoe het punt op een optimale manier kan bereikt worden. (Met optimaal wordt bedoeld: als er een oplossing bestaat met maar 1 knik ipv 2, dan is die eerste beter.)
  3. Practicum bespreken
  4. gegeven: K cirkels met gegeven middelpunt en straal. De cirkels overlappen nergens, maar ze kunnen wel onder/boven/langs elkaar staan. N punten, en ieder punt ligt in een cirkel. Gevraagd: maak een algoritme met tijdscomplexiteit maximum O[(n+k)log(n+k)] om te zoeken welk punt in welke cirkel ligt. (oplossing: gebruik een doorlooplijnalgoritme. ipv het middelpunt van de cirkel te gebruiken zal je het begin en einde van een cirkel in de overgangspuntenlijst moeten steken, dus het punt van de cirkel waarvoor x minimaal is en het punt voor de cirkel waar x maximaal is.)

10/06/2011 namiddag

    • Graadverhoging en variatieverminderingseigenschap, wat is het verband bij Béziercurven?
    • Hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? hoeveel moeten er samenvallen?
  1. Algoritme voor onderbrug geven. werkt dit voor willekeurige startwaarde?
  2. robotarm: = 45 cm, = 30 cm en = 25 cm en het te bereiken punt op 20 cm van de schouder. Leg uit hoe het punt op een optimale manier kan bereikt worden.
  3. Practicum bespreken
  4. #oefening:gegeven: een aantal cirkels met gegeven middelpunt en straal. Zoek of er cirkels zijn die snijden, maar cirkels die volledig in een andere cirkel zit snijdt niet. Bespreek eerst hoe je het gaat doen, en geef dan een ruw algoritme in pseudocode. Er bestaat een doorlooplijnalgoritme van O(nlogn).

07/06/2010 voormiddag

  1. Bespreek de C² continuïteit bij samengestelde Béziercurven
  2. Geef de eigenschappen die ervoor zorgen dat een EMDB kan worden gevonden in O(nlogn). Bewijs één van deze eigenschappen
  3. Ik heb een robotarm bestaande uit 3 verbindingen (zogenaamde 'links'). De lengtes van de verbindingen zijn = 70cm, = 20 cm en = 30 cm (in deze volgorde). Leg uit hoe een gegeve punt dat op 25 centimeter van de schouder ligt op een optimale manier kan bereikt worden.
  4. Practicum bespreken
  5. Geef een algoritme dat in O(nlogn) voor een verzameling van n vierkanten bepaalt of er overlappingen zijn. Van de vierkanten zijn het linkerbeneden- en het rechterbovenhoekpunt gegeven.

28/08/2009 voormiddag

  1. Wat is het algoritme van de Cassteljau (voor Béziercurven) en het algoritme van de Boor? Wat zijn de gelijkenissen en de verschillen? Hoe bewijs je het algoritme van de Casteljau?
  2. Doorlooplijnalgoritme voor het bepalen van een Voronoi-diagramma. Welke soorten overganspunten komen voor, hoe kunen ze bepaald worden en welke acties moeten ondernomen worden als de doorlooplijn door een overgangspunt gaat ?
  3. Ik heb een robotarm bestaande uit 3 verbindingen (zogenaamde 'links'). De lengtes van de verbindingen zijn = 45cm, = 30 cm en = 25 cm (in deze volgorde). Leg uit hoe een gegeve punt dat op 20 centimeter van de schouder ligt op een optimale manier kan bereikt worden.
  4. Gegeven een verzameling circels, bepaal een doorlooplijnalgoritme dat bepaalt of er zich snijdingen voordoen. Dit kan in O(n log(n) )

22/06/2009 namiddag

  1. Bespreek tensor product Bézieroppervlaktesegment + tweede afgeleide
  2. Bespreek het "verdeel-en-heers" algoritme voor dichtstepuntenpaar + rekencomplexiteit
  3. Robotarmoefening: l1=55cm, l2=100cm, l3=75cm met punt op 85cm
  4. Bespreking verslag
  5. Aantal lijnstukken gegeven rond een centraal punt p. Er bestaat een algoritme met roterende rechte door p met rekencomplexiteit O(nlogn). Geef algemene strategie + pseudocode

08/06/2009 namiddag

  1. Bespreek C² continuïteit bij samengestelde béziercurven
  2. EMDB uitleggen
  3. Robotarmoefening met 3 stukken
  4. Bespreking van het verslag.
  5. Gegeven een verzameling van N aantal niet-snijdende lijnstukken en een punt p. Hoe bereken je welke lijnstukken zichtbaar zijn voor p? (Doorlooplijn = roterende rechte door p) (zelfde opgave als 08/06/2009 namiddag).

08/06/2009 (Bart) - Voormiddag

  1. Hoe kan je een spline curve laten interpoleren in een punt door controlepunten te laten samenvallen? Hoeveel en welke controlepunten moeten er samenvallen?
  2. De Voronoi-veelhoek behorende bij een punt Pi element van S is begrensd als en slechts als Pi element van inw(CH(S)).
  3. Minkowski-som (zie oefenzitting 9)
  4. Bespreking van het verslag.
  5. Hoe kan je in O(n) bewerkingen testen of een lijnstuk PiPi+2 een diagonaal is in een eenvoudige veelhoek V = P1 P2...Pn? Een diagonaal is een lijnstuk PiPj dat, op de eindpunten na, volledig in inw(V) ligt. (PiPj snijdt de veelhoek enkel in de punten Pi en Pj). De hoekpunten van V zijn in tegenwijzersin genummerd. Leg eerst de algemene strategie uit, en geef dan een 'hoog niveau' pseudo-code beschrijving van het algoritme. Je hoeft geen rekening te houden met speciale (rand) gevallen.

01/09/2008

  1. Illustruur het algoritme van de Boor, voor n=3, toon correctheid aan. Meetkundige continuïteit is genoeg.
  2. Bewijs: Bij een Voronoi diagramma geldt: Het veelvlak dat hoort bij het gebied rond een site-punt p is begrensd als en slechts als p behoort tot de inwendige van de convex hull rond alle punten p element van S van het Voronoi diagramma.
  3. Minkowski-som en bijhorend sterdiagram tekenen voor een gegeven figuur en robot.
  4. Gegeven een verzameling punten p1...pn. Een verzameling cirkels met middelpunten m1...mk en stralen r1...rk. De cirkels snijden/overlappen elkaar niet. Elk punt ligt in 1 cirkel. Zoek een algoritme dat in O((n+k).log(n+k)) voor elk punt bepaalt tot welke cirkel het behoort. Strategie uitleggen en pseudo-code schrijven.

01/02/2008

  1. Hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? Hoeveel en welke controlepunten moeten er samenvallen?
  2. Uitleggen hoe je het verste puntenpaar van een puntenverzameling kan bepalen in O(n.log(n)). Hoog niveau beschrijving, niet zo gedetailleerd als in de cursus. Verklaar de rekencomplexiteit.
  3. Minkowski-som en bijhorend sterdiagram tekenen voor een gegeven figuur en robot.
  4. Bespreking van het practicum.
  5. Gegeven een verzameling punten p1...pn. Een verzameling cirkels met middelpunten m1...mk en stralen r1...rk. De cirkels snijden/overlappen elkaar niet. Elk punt ligt in 1 cirkel. Zoek een algoritme dat in O((n+k).log(n+k)) voor elk punt bepaalt tot welke cirkel het behoort. Strategie uitleggen en pseudo-code schrijven.

18/01/2008 (1)

  1. Bespreek hoe men C²-continuïteit kan bekomen bij samengestelde Bézier-curven
  2. Hoe kan je de Euclidische Minimale Opspannende Boom van een puntenverzameling in O(n lg n) berekenen? Geef daarbij duidelijk aan op basis van welke eigenschappen je dit doet.
  3. Robotarm met L1=70cm, L2=20cm, L3=30cm en het punt p op 25cm van de schouder van het arm.
  4. Bespreking van het practicum
  5. Gegeven een verzameling van n niet-snijdende lijnstukken en een punt P die niet op één van de lijnstukken ligt, bepaal in O(n lg n) alle lijnstukken die zichtbaar zijn vanuit P.

18/01/2008 (2)

  1. Hoe kan men interpolatie bekomen bij splines door middel van samennemen van knooppunten
  2. Voronoi doorlooplijnalgoritme met fortune: wat zijn overgangspunten en bespreek welke acties er moeten ondernomen worden.
  3. robotarm met L1=45, L2=25 en L3=30
  4. bespreking practicum
  5. gegeven een aantal cirkels: geef een efficiente berekening (n log2(n) ) voor het bepalen of er snijdende cirkels zijn.

--> HINT: Gebruik niet de middelpunten bij een doorlooplijn, maar de uiterste linkse waarden (x+r) en de uiterste rechtse waarden (x-r) van de cirkel bij een doorlooplijn van links naar rechts

04/09/2007

  1. bespreek subdivisie + methode + continuiteit vwd + nut van subdivisie
  2. geef een algoritme voor de berekening van het VPP van een vz van N punten in O(nlog n) bewerkingen verantwoord de rekencomplexiteit
  3. minowski som tekenen op figuur met bijhorende sterdiagram + extra uitleegt hoe aan de oplossing bekomen bent.
  4. bespreking practicum
  5. gegeven een aantal vierhoeken met zijn linkeronder-hoekpunt en zijn rechteboven-hoekpunt nagaan of ze geheel of gedeeltelijk overlappen (uitleg + hoog niveau algo)in O(nlog (n)) bewerkingen.

21/08/2007

  1. Bespreek continuiteit.
  2. Voronoi doorlooplijnalgoritme: bespreek de overgangspunten, hoe je weet waar ze zijn, en welke acties je moet ondernemen als je een tegenkomt. (vergeet niet het bijvoegen en verwijderen van cirkelevents als er een boog bijkomt of verdwijnt)
  3. minowski som tekenen op figuur met bijhorende sterdiagram
  4. bespreking practicum
  5. oefening:gegeven: een aantal cirkels met gegeven middelpunt en straal. Zoek of er cirkels zijn die snijden, maar cirkels die volledig in een andere cirkel zit snijdt niet. Bespreek eerst hoe je het gaat doen, en geef dan een ruw algoritme in pseudocode. Er bestaat een doorlooplijnalgoritme van O(nlogn). (oplossing: denk aan snijdende lijnenalgoritme, en om de complexiteit goed te krijgen hou je een gesorteerde boom bij met al de onderste van de cirkels, en een met alle bovenste, en zo vergelijk je met boven en onder).

15/06/2007

  1. hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? hoeveel controlepunten moeten er samenvallen?
  2. verste puntenpaar algoritme
  3. minowski som tekenen op figuur met bijhorende sterdiagram
  4. bespreking practicum
  5. algoritme om te bepalen welke punten ... in welke cirkel ... met stralen ... zit waarbij geen punten uit de cirkels zitten en in O(n+k n+k) opgelost moet worden


15/06/2007

  1. hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? hoeveel controlepunten moeten er samenvallen?
  2. Voronoi doorlooplijnalgoritme: bespreek de overgangspunten, hoe je weet waar ze zijn, en welke acties je moet ondernemen als je een tegenkomt. (vergeet niet het bijvoegen en verwijderen van cirkelevents als er een boog bijkomt of verdwijnt)
  3. een oefening met een robotarm met drie delen (L1:90cm, L2:50cm, L3:65 cm) en een punt op 35 cm van middelpunt (oplossing: deel 2 en deel 3 samennemen)
  4. bespreking practicum
  5. oefening:gegeven: een aantal cirkels met gegeven middelpunt en straal. Zoek of er cirkels zijn die snijden, maar cirkels die volledig in een andere cirkel zit snijdt niet. Bespreek eerst hoe je het gaat doen, en geef dan een ruw algoritme in pseudocode. Er bestaat een doorlooplijnalgoritme van O(nlogn). (oplossing: denk aan snijdende lijnenalgoritme, en om de complexiteit goed te krijgen hou je een gesorteerde boom bij met al de onderste van de cirkels, en een met alle bovenste, en zo vergelijk je met boven en onder).

19/06/2006 Voormiddag

  1. Hoe verkrijgen we continuiteit bij bézier curven? Leg uit.
  2. Welk soorten events zijn er bij het algoritme van Fortune. Welke acties moeten er gebeuren en hoe plannen we ze?
  3. 3-link probleem oplossen voor drie gegeven armen en punt. = 90cm, = 50cm, = 65cm. Eindpunt ligt op 35 cm van schouder.
  4. Practicum bespreking
  5. Gegeven een verzameling cirkels. Ontwerp een algoritme om te bepalen of er cirkels snijden. Leg eerst je strategie uit en geef dan pseudo-code. Er bestaat een doorlooplijnalgoritme met O(n log n). (Allemaal gegeven)

Minder recente examens

07/06/2004, voormiddag

  1. continuiteit bij bézier-curve. Wat? Hoe?

    • afleiden, invullen linkercurve t=1; rechtercurve t=0
    • nultermen schrappen... Gelijkstellen... de verhoudingen rollen eruit... in de formule is trouwens de lengte van het interval waarvoor dat segement geldt...
  2. Voronoi-doorlooplijn-algoritme (Fortune)
    Wat zijn de 'events'; hoe vind je ze, welke acties moeten er bij welke events gedaan worden? Exhaustief zijn, maar beknopt in de uitleg bij de acties.
    • site-events... circle-events toevoegen en verwijderen...
    • circle-events... circle-events toevoegen en verwijderen... you know the drill
  3. Minkowski-som maken... zeer gelijkaardige figuur dan gelijk bij oefenzitting 9. Via sterdiagram.
  4. N Punten op een cirkel. Zoek de grootste driehoek.
    • Strategie:
      • Doorloop driehoeken met basis 2 opeenvolgende punten; dan met 1 pt. ertussen; ... tot N/2.
      • Voor die voorwaarde op de basis, telkens rondlopen gelijkaardig aan de tegenvoetersparen van het verste-puntenpaar-probleem. => Je kan de tegenvoeter van de vorige gebruiken bij de volgende, ... voor dezelfde basis.
      • onthoud doorheen het algo de grootste driehoek.
    • Hoog-niveau-algoritme. -> triviaal
    • Complexiteit:
      • sorteer de punten naar stijgende poolhoek :Nlog(N)
      • buitenste lus N/2
      • binnenste lus N
      • allerbinnenste lus: O(1)
      • => totaal O(NlogN + N²) => O(N²)
  5. Bespreking van het practicum.


Oefeningen

oefening uit laatste oefenzitting

Laatste oefenzitting
http://static.flickr.com/70/152994638_00c7b383d1_m.jpg http://static.flickr.com/74/152994136_19ebb442d2_m.jpg http://static.flickr.com/52/152993572_347a6fb5af_m.jpg

Oefening op bepalen van het aantal snijpunten

bepalen van alle snijpunten in een willekeurige verzameling lijnstukken (klik voor groter)

Gegeven: een willekeurige verzameling lijnstukken
Gevraagd: vind een algoritme dat ALLE snijpunten vindt
Oplossing: iemand?

Misschien is dit een oplossing. Gebruik het algoritme uit de cursus dat true of false teruggeeft als er twee of meerdere lijnstukken in een set snijden. Maak van return false een commando dat het gevonden snijpunt opslaagt in een output vector. Er is volgens mij wel nog een probleem: Wanneer er meerdere snijpunten vallen tussen 2 begin of eindpunten. Waarschijnlijk moet je ook op intersecties testen bij eindpunten (maar wel geen dubbels toevoegen aan de output) Het zou kunnen dat dat genoeg is. Heb het nog niet nagekeken voor alle gevallen. Anders is nog een andere oplossing: elk snijpunt dat je vindt toevoegen als een locatie waar de doorlooplijn moet geevalueerd worden, snijpunt 2x toevoegen aan T (voor elk van de betrokken lijnstukken) waarbij je zorgt dat het lijnstuk dat bovenaan stond nu beneden staat (op dit moment snijden ze de doorlooplijn op hetzelfde punt, maar hierachter wisselen ze van plaats) en beginpunten van de 2 betrokken rechten verwijderen.

Idee: zoals bovenstaande persoon zei: neem doorlooplijnalgoritme, ipv. return true hou je de koppels lijnstukken bij, en controleer achteraf op dubbels. Haal deze eruit, et voilla.

Opmerking: bij het vinden van een snijpunt moeten de snijdende rechten verwisseld worden in de doorlooplijnstatus! (anders ga je niet alle snijpunten vinden)

Oefeningen links

De pagina met de opgaven van de oefenzittingen en van het practicum, alsook links naar extra informatie.

Bevat ook alle links die in de cursus vermeld worden. http://www.cs.kuleuven.be/~krisd/TMI/