25th Multimedia Exposition in
Computational Geometry

This year, like the previous year, the multimedia exposition in computational geometry is distributed on the web only. The videos and interactive demos are available in one of the original formats provided by the authors.
Click presentation titles for a link to the accompanying paper on the LIPIcs-Server. These short papers appeared in the Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), and are available through the LIPIcs online proceedings.

Multimedia

• Interactive Geometric Algorithm Visualization in a Browser
  Lynn Asselin, Kirk P. Gardner, and Donald R. Sheehy
  We present an online, interactive framework for writing and presenting interactive geometry demos suitable for classroom demonstrations. The tool provides code for simple data structures that can describe planar geometry, polyhedral surfaces, and even more complex topological surfaces. Our intention is to provide users with a framework to visualize and interact with geometric algorithms without writing any explicit interaction or visualization code. We hope this project will be beneficial to educators and students alike, allowing a clear interactive visual aid to procedures that would otherwise be presented in a textbook or lecture slide.
  Play online
  Play online on github | Download from the authors' site (zip, 10 Mb)
• Geometric Models for Musical Audio Data
  Paul Bendich, Ellen Gasparovic, John Harer, and Christopher Tralie
  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.
  Play online
  Play online on the authors' site | Download from the authors' site (zip, 10 Mb)
• Visualizing Scissors Congruence
  Satyan L. Devadoss, Ziv Epstein, and Dmitriy Smirnov
  Consider two simple polygons with equal area. The Wallace-Bolyai-Gerwien theorem states that these polygons are scissors congruent, that is, they can be dissected into finitely many congruent polygonal pieces. We present an interactive application that visualizes this constructive proof.
  Play online
  Play online on github | Download from the authors' github repository (zip, 1 Mb)
• Visualization of Geometric Spanner Algorithms
  Mohammad Farshi and Seyed Hossein Hosseini
  The tool presented herein consists of visualization of four t-spanner algorithms‎: ‎path-greedy‎, ‎gap-greedy‎, ‎$\Theta$-graph and Yao-graph. ‎This visualization animates the steps of the algorithms (with adjustable speed) on a given point set, export the network generated by the algorithms to‎ .‎ipe format‎. The visualization is browser-independent and it does not require extension to be installed on a web browser‎. ‎One can use it on any modern browser‎, ‎including iOS devices like the iPhone and iPad‎, ‎android devices such as smart watches and TVs‎, ‎and even the web browser on Kindle‎.
  Play online
  Play online on the authors' site | Download from the authors' site (rar, 1 Mb)
• Path Planning for Simple Robots using Soft Subdivision Search
  Ching-Hsiang Hsu, John Paul Ryan, and Chee Yap
  We introduce the Soft Subdivision Search (SSS) framework for designing a new class of path planning algorithms, founded on the concept of resolution-exactness. This video illustrates the SSS framework for a trio of simple planar robots: disc, triangle and 2-links. These algorithms achieves state-of-art real-time performance, and are relatively easy to implement.
  mp4 (71 Mb)
• Exploring Circle Packing Algorithms
  Kevin Pratt, Connor Riley, and Donald R. Sheehy
  A circle packing of an undirected, planar graph consists of an assignment of radii to the vertices of the graph. From these radii the graph may be embedded in the plane with vertices represented by circles of the associated radius, such that the incidence of two vertices is reflected by the tangency of two circles, and all circles are interior-disjoint. We present an interactive tool for visualizing circle packing algorithms. The tool contains four visualization modes which allow the user to explore Möbius transformations, a stereographic projection, and the dual graph of a weighted Delaunay triangulation.
  Download from the authors' github repository (zip, 29 Mb). This project is run using Processing. Open the Demo.pde file with Processing and press the 'play' button to begin.
• The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation
  Wouter van Toll, Atlas F. Cook IV, Marc J. van Kreveld, and Roland Geraerts
  We present the Explicit Corridor Map (ECM), a navigation mesh for path planning and crowd simulation in virtual environments. For a 2D or multi-layered 3D environment with polygonal obstacles, the ECM is the medial axis of the free space annotated with nearest-obstacle information. It can be used to compute short and smooth paths for disk-shaped characters of any radius. In our abstract, we define the ECM and various geometric operations that can be applied to it, and we describe how we have implemented a real-time crowd simulation framework around the ECM. This software has been used to simulate real-life events involving large crowds. Our demo application shows a single moving character and displays various features of the ECM.
  Download from the authors' site (zip, 0.6 Mb) The zip contains an executable .exe file.
• High Dimensional Geometry of Sliding Window Embeddings of Periodic Videos
  Christopher J. Tralie
  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.
  mp4 (60 Mb)
• Introduction to Persistent Homology
  Matthew L. Wright
  This video presents an introduction to persistent homology, aimed at a viewer who has mathematical aptitude but not necessarily knowledge of algebraic topology. Persistent homology is an algebraic method of discerning the topological features of complex data, which in recent years has found applications in fields such as image processing and biological systems. Using smooth animations, the video conveys the intuition behind persistent homology, while giving a taste of its key properties, applications, and mathematical underpinnings.
  mp4 (70 Mb)

Recommended Video Player

VLC (available for Windows, Mac, Linux) can play all of this year's video submissions.

Credits

These multimedia presentations were selected from the submissions by the following multimedia program committee:

Martin Demaine, MIT, USA
William Evans, University of British Columbia, Canada
Michael Hoffmann, ETH Zürich, Switzerland
Irina Kostitsyna, TU Eindhoven, the Netherlands
Maarten Löffler (chair), Utrecht University, The Netherlands
Martin Nöllenburg, TU Wien, Austria
Don Sheehy, University of Connecticut, USA
Birgit Vogtenhuber, TU Graz, Austria

---

25th Multimedia Exposition in Computational Geometry CG Week 2016