Finding The Destruction Path of Line of Godzillas That's Rampaging Philadelphia

by Rich Berger, Vincent Ha, David Kratz, Michael Lin, and Jeremy Moyer at Ursinus College

A group of news anchors struggles to find the correct data structure to efficiently send out an early warning to the residents of Philadelphia who will be overtaken by a marching line of Godzillas. After exploring several options, the group eventually settles on onions and fractional cascading. But what do they discover?? Watch the video below to find out!

Godzilla Onions And Fractional Cascading Demo

by Chris Tralie

The interactive applet below shows the steps of the onions + fractional cascading data structure construction and query, which our above heroes used in our time of need. For N points in the plane and h points above the line, the data structure enables output-sensitive O(log(N) + h) queries.