3 Search Results for "Tralie, Christopher"

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-dev.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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.65
Geometric Models for Musical Audio Data

Authors: Paul Bendich, Ellen Gasparovic, John Harer, and Christopher Tralie

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We study the geometry of sliding window embeddings of audio features that summarize perceptual information about audio, including its pitch and timbre. These embeddings can be viewed as point clouds in high dimensions, and we add structure to the point clouds using a cover tree with adaptive thresholds based on multi-scale local principal component analysis to automatically assign points to clusters. We connect neighboring clusters in a scaffolding graph, and we use knowledge of stratified space structure to refine our estimates of dimension in each cluster, demonstrating in our music applications that choruses and verses have higher dimensional structure, while transitions between them are lower dimensional. We showcase our technique with an interactive web-based application powered by Javascript and WebGL which plays music synchronized with a principal component analysis embedding of the point cloud down to 3D. We also render the clusters and the scaffolding on top of this projection to visualize the transitions between different sections of the music.
Cite as

Paul Bendich, Ellen Gasparovic, John Harer, and Christopher Tralie. Geometric Models for Musical Audio Data. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 65:1-65:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bendich_et_al:LIPIcs.SoCG.2016.65,
  author =	{Bendich, Paul and Gasparovic, Ellen and Harer, John and Tralie, Christopher},
  title =	{{Geometric Models for Musical Audio Data}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{65:1--65:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.65},
  URN =		{urn:nbn:de:0030-drops-59577},
  doi =		{10.4230/LIPIcs.SoCG.2016.65},
  annote =	{Keywords: Geometric Models, Audio Analysis, High Dimensional Data Analysis, Stratified Space Models}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.71
High-Dimensional Geometry of Sliding Window Embeddings of Periodic Videos

Authors: Christopher Tralie

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We explore the high dimensional geometry of sliding windows of periodic videos. Under a reasonable model for periodic videos, we show that the sliding window is necessary to disambiguate all states within a period, and we show that a video embedding with a sliding window of an appropriate dimension lies on a topological loop along a hypertorus. This hypertorus has an independent ellipse for each harmonic of the motion. Natural motions with sharp transitions from foreground to background have many harmonics and are hence in higher dimensions, so linear subspace projections such as PCA do not accurately summarize the geometry of these videos. Noting this, we invoke tools from topological data analysis and cohomology to parameterize motions in high dimensions with circular coordinates after the embeddings. We show applications to videos in which there is obvious periodic motion and to videos in which the motion is hidden.
Cite as

Christopher Tralie. High-Dimensional Geometry of Sliding Window Embeddings of Periodic Videos. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 71:1-71:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{tralie:LIPIcs.SoCG.2016.71,
  author =	{Tralie, Christopher},
  title =	{{High-Dimensional Geometry of Sliding Window Embeddings of Periodic Videos}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{71:1--71:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.71},
  URN =		{urn:nbn:de:0030-drops-59630},
  doi =		{10.4230/LIPIcs.SoCG.2016.71},
  annote =	{Keywords: Video Processing, High Dimensional Geometry, Circular Coordinates, Nonlinear Time Series}
}
  • Refine by Author
  • 2 Tralie, Christopher
  • 1 Bendich, Paul
  • 1 Berger, Richard
  • 1 Gasparovic, Ellen
  • 1 Ha, Vincent
  • Show More...

  • Refine by Classification
  • 1 Human-centered computing → Visualization toolkits
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 1 Audio Analysis
  • 1 Circular Coordinates
  • 1 Geometric Models
  • 1 High Dimensional Data Analysis
  • 1 High Dimensional Geometry
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2016
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact