DROPS

Document

Media Exposition

DOI: 10.4230/LIPIcs.SoCG.2024.90

Visualizing Lucas’s Hamiltonian Paths Through the Associahedron 1-Skeleton (Media Exposition)

Authors: Kacey Thien-Huu La, Jose E. Arbelo, and Christopher J. Tralie

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

We re-examine the 1987 paper by Joan Lucas[Lucas, 1987], who showed that the edge-flip graph of convex polygon triangulations is Hamiltonian. We focus specifically on the first part of her paper on Hamiltonian paths, and we provide a simplified algorithm for that case which elucidates how to assemble a recursive subdivision that she refers to as "stacks." Finally, we provide an interactive web-based visualization of Hamiltonian paths through the stacks.

Cite as

Kacey Thien-Huu La, Jose E. Arbelo, and Christopher J. Tralie. Visualizing Lucas’s Hamiltonian Paths Through the Associahedron 1-Skeleton (Media Exposition). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 90:1-90:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{la_et_al:LIPIcs.SoCG.2024.90,
  author =	{La, Kacey Thien-Huu and Arbelo, Jose E. and Tralie, Christopher J.},
  title =	{{Visualizing Lucas’s Hamiltonian Paths Through the Associahedron 1-Skeleton}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{90:1--90:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.90},
  URN =		{urn:nbn:de:0030-drops-200355},
  doi =		{10.4230/LIPIcs.SoCG.2024.90},
  annote =	{Keywords: associahedron, hamiltonian paths, visualization, tree rotations, convex polygons}
}

Document

Media Exposition

DOI: 10.4230/LIPIcs.SoCG.2023.62

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

Authors: Richard Berger, Vincent Ha, David Kratz, Michael Lin, Jeremy Moyer, and Christopher J. Tralie

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

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/

Cite as

Richard Berger, Vincent Ha, David Kratz, Michael Lin, Jeremy Moyer, and Christopher J. Tralie. Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 62:1-62:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.SoCG.2023.62},
  URN =		{urn:nbn:de:0030-drops-179129},
  doi =		{10.4230/LIPIcs.SoCG.2023.62},
  annote =	{Keywords: convex hulls, onions, fractional cascading, visualization, d3}
}

Search Results

Documents authored by Tralie, Christopher J.

Visualizing Lucas’s Hamiltonian Paths Through the Associahedron 1-Skeleton (Media Exposition)

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message