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!
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.