2026-07-23T21:56:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17912 2024-03-06T11:00:41Z ddc:004 open_access

Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading (Media Exposition) Berger, Richard Ha, Vincent Kratz, David Lin, Michael Moyer, Jeremy Tralie, Christopher J. convex hulls onions fractional cascading visualization d3 We provide a skit and an applet to illustrate fractional cascading in the context of half-plane range search for points in the Euclidean plane, which takes O(log N + h) output-sensitive time. In the video, 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, only to discover that they themselves are in the line of fire! In the applet, we show step by step details of preprocessing to build the onions with fractional cascading and the subsequent query of the "Godzilla line" against the onion layers. Our video skit and applet can be found at https://ctralie.github.io/GodzillaOnions/ Schloss Dagstuhl – Leibniz-Zentrum für Informatik Richard Berger and Vincent Ha and David Kratz and Michael Lin and Jeremy Moyer and Christopher J. Tralie 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.62 urn:nbn:de:0030-drops-179129 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.62 eng https://creativecommons.org/licenses/by/4.0/legalcode