License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2023.62
URN: urn:nbn:de:0030-drops-179129
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17912/
Go to the corresponding LIPIcs Volume Portal

Berger, Richard ; Ha, Vincent ; Kratz, David ; Lin, Michael ; Moyer, Jeremy ; Tralie, Christopher J.

Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading (Media Exposition)

pdf-format:
LIPIcs-SoCG-2023-62.pdf (0.5 MB)

Abstract

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/

BibTeX - Entry

@InProceedings{berger_et_al:LIPIcs.SoCG.2023.62,
  author =	{Berger, Richard and Ha, Vincent and Kratz, David and Lin, Michael and Moyer, Jeremy and Tralie, Christopher J.},
  title =	{{Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{62:1--62:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17912},
  URN =		{urn:nbn:de:0030-drops-179129},
  doi =		{10.4230/LIPIcs.SoCG.2023.62},
  annote =	{Keywords: convex hulls, onions, fractional cascading, visualization, d3}
}

Keywords: convex hulls, onions, fractional cascading, visualization, d3
Collection: 39th International Symposium on Computational Geometry (SoCG 2023)
Issue Date: 2023
Date of publication: 09.06.2023
Supplementary Material: Software (Source Code): https://ctralie.github.io/GodzillaOnions/

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI