COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@csc.uvic.ca). To get email notification of our seminars and other events, you can subscribe to the CAG email list at http://mailman.csc.uvic.ca/mailman/listinfo/cag
Date  Place  Time  Speaker  Abbreviated Title 

Fri. June 8  EOW 430  2:30pm  John Ellis  Turing's Seminal 1936 Paper 
Fri. June 22  all day  Turing Celebration Day  
Friday June 29  DSB C 112  2:30pm  Zahed Rahmati  Kinetic Pie Delaunay Graph and its Applications 
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 2dimensional 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^{2}λ_{2s+2}(sn) β_{s+2}(n)) events for the YG and O(n^{2}λ_{2s+2}(sn)) events for the EMST, each in O(log^{2} n) time. Here, λ_{s}(n) = nβ_{s}(n) is the maximum length of DavenportSchinzel sequences of order s on n symbols.
Our KDS processes nearly cubic events for the EMST which improves the previous bound O(n^{4}) by Rahmati et al.