CAG Schedule of Talks: Summer 2012

COMBINATORIAL ALGORITHMS GROUP
Schedule of Talks: Summer 2012

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

Schedule for Talks:

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

Previous Talks

Turing's Seminal 1936 Paper
John Ellis
Friday June 8, 2:30-3:30pm, EOW 430

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.

Alan Turing's 100th Birthday Celebration
A DAY OF FREE PUBLIC EVENTS
Friday, June 22nd, 2012, ECS 660

June 23, 2012 marks the 100th birthday of Alan Turing, the "father" of computer science and artificial intelligence, whose ideas formalized our notion of computation and algorithms. He also created designs for some of the first computers and devised techniques for breaking the Enigma ciphers used by the Germans during WWII.
People are celebrating Turing's 100th birthday around the world: http://www.mathcomp.leeds.ac.uk/turing2012/
We would like to invite you to turing100@uvic.ca! Spend the day talking about Turing's tremendous accomplishments! Vist this web page for more information:
http://www.csc.uvic.ca/Events/turing100.htm

Kinetic Pie Delaunay Graph and its Applications
Zahed Rahmati
Friday June 29, 2:30pm in DSB C 112

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(n2λ2s+2(sn) βs+2(n)) events for the YG and O(n2λ2s+2(sn)) events for the EMST, each in O(log2 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(n4) by Rahmati et al.


CAG Schedule of Talks: Summer 2012 / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised June 14, 2012