Accepted Multimedia Presentations

All videos can be found at computational-geometry.org

  • Lynn Asselin, Kirk P. Gardner, and Donald R. Sheehy
        Interactive Geometric Algorithm Visualization in a Browser [+]
    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.
  • Paul Bendich, Ellen Gasparovic, John Harer, and Christopher Tralie
        Geometric Models for Musical Audio Data [+]
    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.
  • Satyan L. Devadoss, Ziv Epstein, and Dmitriy Smirnov
        Visualizing Scissors Congruence [+]
    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.
  • Mohammad Farshi and Seyed Hossein Hosseini
        Visualization of Geometric Spanner Algorithms [+]
    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.
  • Ching-Hsiang Hsu, John Paul Ryan, and Chee Yap
        Path Planning for Simple Robots using Soft Subdivision Search [+]
    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.
  • Kevin Pratt, Connor Riley, and Donald R. Sheehy
        Exploring Circle Packing Algorithms [+]
    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.
  • Wouter van Toll, Atlas F. Cook IV, Marc J. van Kreveld, and Roland Geraerts
        The Explicit Corridor Map: Using the Medial Axis for Real-Time Path
         Planning and Crowd Simulation [+]
    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.
  • Christopher J. Tralie
        High Dimensional Geometry of Sliding Window Embeddings of
         Periodic Videos [+]
    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.
  • Matthew L. Wright
        Introduction to Persistent Homology [+]
    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.


Multimedia Exposition

Multimedia presentations are sought for the 25th International Computational Geometry Multimedia Exposition, which will take place in June as part of Computational Geometry Week 2016. Computational Geometry Week also encompasses the 32nd International Symposium on Computational Geometry. The Multimedia Exposition showcases the use of visualisation in computational geometry for exposition and education, for visual exploration of geometry in research, and as an interface and a debugging tool in software development.

Content and Form

The content of multimedia presentations should be related to computational geometry or neighbouring areas, but is otherwise unrestricted. We encourage submissions that support papers submitted to the Symposium on Computational Geometry, but this is not required. In particular, results being presented are not required to be new. We explicitly encourage submissions that take new views on classic results from computational geometry, which may help to make such results more widely accessible.

The form of multimedia presentations can be anything other than the traditional paper or slide show. Algorithm animations, visual explanations of structural theorems, descriptions of applications of computational geometry, demonstrations of software systems, and games that illustrate concepts from computational geometry are all appropriate. There are no limitations on creativity, anything that leverages the possibilities of multimedia to enlighten and entertain the viewer while learning about computational geometry or neighbouring areas will do. This includes rendered animation, films with narrators and/or actors, and interactive stories, as well as interactive demos.

Quality Issues

The "format" as well as the creative content of Multimedia submissions influences their acceptance. For videos, a length of three to five minutes is usually ideal; ten minutes is the upper limit. For the final version, we require video in 720P or better, using H.264. The embedded audio stream should be AAC of at least 128kBit/s. Telephone-sounding audio (limited frequency range, noise) or live rooms, as often recorded with cheap headsets, must be avoided, as well as speakers with too heavy accent. Interactive applications (e.g., HTML5, Flash, AIR, Java, etc.) should provide a "demo" mode where they run by themselves. They should be submitted as a distributable package.

To conserve resources, multimedia submissions are limited to 100Mb. Authors are free to post higher quality versions on their own web sites, and we will include links in the electronic proceedings to their version, in addition to the official (<100MB) version archived on computational-geometry.org.

It is strongly encouraged to contact the CG:MM PC well in advance to 1) discuss the quality of a video submission (based on sample files) or 2) to present your non-video idea and how it could be reviewed, presented, and distributed.

Submission

Submissions should be deposited online where they are accessible through the web or via FTP. A video submission should play trouble-free on programs like VLC Media Player. For ease of sharing and viewing, we encourage (but do not require) that each video submission be uploaded to YouTube, and that the corresponding URL be included with the submission.

Each submission should include a description of at most four pages of the material shown in the presentation, and where applicable, the techniques used in the implementation. This four-page description must be formatted according to the guidelines for the conference proceedings, using the LIPIcs format. LIPIcs typesetting instructions can be found at http://www.dagstuhl.de/en/publications/lipics and the lipics.cls LaTeX style file at http://drops.dagstuhl.de/styles/lipics/lipics-authors.tgz.

Send a mail to the CG:MM chair, Maarten Löffler (m.loffler at uu.nl) by February 24, 2016, with the following information:

  • the names and institutions of the authors
  • the email address of the corresponding author
  • instructions for downloading the submission
  • if available: the link to the YouTube video
  • and the PDF abstract.

We explicitly encourage multimedia submissions that support papers submitted to the Symposium. However, submitted papers and associated multimedia submissions will be treated entirely separately by the respective committees: acceptance or rejection of one will not influence acceptance or rejection of the other. Authors will be notified of acceptance or rejection, and given reviewers' comments, by March 16, 2016. For each accepted submission, the final version of the 4-page textual description will be due by March 23, 2016 for inclusion in the proceedings. Final versions of accepted multimedia presentations will be due April 27, 2016.

Important Dates

February 24, 2016: Multimedia submissions due
March 16, 2016: Notification of acceptance/rejection
March 23, 2016: Camera-ready versions due for abstracts
April 27, 2016: Final versions due for multimedia
June 14-17, 2016: CGWeek 2016

All deadlines are 23:59 anywhere on earth.

Multimedia 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