Thesis defense by Theodosios Kalfas – Københavns Universitet

Thesis defense by Theodosios Kalfas

Master Thesis Defence by Theodosios Kalfas

Title: Euclidean Minimal Steiner Trees for Moving Points

Abstract

Kinetic data structures have been used in order to model continuous motion of geometric objects, based on the occurrence of discrete events. Motion of the geometric objects in two dimensions is defined by algebraic functions of constant maximum degree. We examine the possibility of utilizing existing kinetic data structures in order to be able to maintain a Euclidean Steiner minimal tree for moving points.
It is computationally hard to obtain an exact solution for the Euclidean Steiner minimal tree problem,therefore heuristics are often used. Our approach is to study existing heuristics for the problem, and investigate whether it is possible to maintain a Euclidean Steiner minimal tree, using the kinetic framework. The resulting data structure shows that some aspects of the heuristics of the static case can be maintained efficiently, while others are still hard to kinetize.

  • Time and Place: September 29, 3pm, DIKU, HCØ, room 01-0-029
  • Supervisor: Pawel Winter
  • External examiner: Jesper Larsen, DTU