[Colloquium] Turkoglu/Dissertation Defense/Jun 2, 2011

[Margaret Jaffey]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Duru Turkoglu

Date:  Thursday, June 2, 2011

Time:  3:00 PM

Place:  Ryerson 277

Title: Stable Algorithms and Kinetic Mesh Refinement

Abstract:
There has been an increasing interest in developing dynamic and
kinetic algorithms as real world applications require computing
certain properties of a given input as it is modified because of
insertions and deletions (dynamic) or because of continuous motion
(kinetic). Considering the static version of the dynamic and kinetic
problems when the input is not allowed to change, in many instances,
the static version of a problem is well understood while the dynamic
and/or kinetic versions are much harder to develop. In order to expand
our intuition on algorithms that are required to handle several types
of modifications, including dynamic and kinetic, Acar et al. recently
proposed an alternative framework called self-adjusting computation.
Given an algorithm that solves the static version of a dynamic or
kinetic problem, the principal algorithmic technique of the
self-adjusting computation framework, called change propagation,
utilizes this static algorithm to generate an update algorithm for the
same problem. The effectiveness of the update algorithm generated by
this approach directly depends on the stability of the static
algorithm: an algorithm is stable if its executions with two similar
inputs produces outputs and intermediate data that are different only
by a small fraction.

In this thesis, we utilize the stability approach and design update
algorithms inspired by change propagation for solving certain dynamic
and kinetic problems in computational geometry. One of the most
interesting of these problems is the problem of kinetically
maintaining a mesh of continuously moving points; we provide a first
result on this long standing open problem. All the results we get in
this thesis indicate that the stability approach in designing dynamic
and kinetic algorithms alleviate the complexity of the update
algorithms and transfer the inherent complexity to the stable design
and analysis of a static solution in order to obtain effective update
algorithms.

Duru's advisors are Prof. Janos Simon and Prof. Umut Acar

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#duru

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=