TU Wien:Algorithmic Geometry VU (Nöllenburg)/Prüfung 2022-02-23

Prüfung 2022-02-23

• Sweep Line Algorithms
  • Data structures
  • Method of the sweep line
  • Events and event handling
  • Line segment intersection algorithm

• Point-Line-Duality
  • How can we transform points/lines from the primal plane to their dual in the dual plane?
  • Which properties does this transformation have?
  • Lower envelope computation by using duality transformation and upper convex hull algorithm

• Range Query of Points
  • kd-Tree
    • Construction time
    • Query time
    • Space
    • How to construct a kd-tree?
  • Range Tree
    • Construction time
    • Query time
    • Space
    • How to construct a range tree?
  • Extensions to 3-dimensions of kd-tree and range tree