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
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.
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 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
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 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 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 PlayerVLC (available for Windows, Mac, Linux) can play all of this year's video submissions.
CreditsThese 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