COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2012

In 1936 a paper was published that thrust the author into the company of leaders in the study of the foundations of mathematics and logic. The author was Alan Turing, at that time a graduate student at the University of Cambridge. In this talk I will survey this historic paper, look at what was done, how it was done and why it forms a foundation for computer science to this day.

This presentation will be a shorter version of that to be given during the Turing celebration planned by the CS department for later in the month.

We construct a new proximity graph, called the Pie Delaunay graph, on a set of n points which is a super graph of Yao Graph and Euclidean minimum spanning tree (EMST). We efficiently maintain the PDG where the points are moving in the plane. We use the kinetic PDG to create a kinetic data structure (KDS) for maintenance of the YG and the EMST on a set of n moving points in 2-dimensional space. Assuming x and y coordinates of the points are defined by algebraic functions of at most degree s, the structure uses O(n) space, O(n log n) preprocessing time, and processes O(n²λ_2s+2(sn) β_s+2(n)) events for the YG and O(n²λ_2s+2(sn)) events for the EMST, each in O(log² n) time. Here, λ_s(n) = nβ_s(n) is the maximum length of Davenport-Schinzel sequences of order s on n symbols.

Our KDS processes nearly cubic events for the EMST which improves the previous bound O(n⁴) by Rahmati et al.