Program – Multimedia Exposition

Listed in no particular order.
Clicking the “[+]” after the title will show the abstract for that multimedia submission.

  • Tilt: The Video - Designing Worlds to Control Robot Swarms with only Global Signals  [+]
    Aaron Becker, Erik Demaine, Sandor Fekete, Hamed Shad, and Rose Morris-Wright.

    Abstract: We present fundamental progress on the computational universality of swarms of micro- or nano- scale robots in complex environments, controlled not by individual navigation, but by a uniform global, external force. More specifically, we consider a 2D grid world, in which all obstacles and robots are unit squares, and for each actuation, robots move maximally until they collide with an obstacle or another robot. The objective is to control robot motion within obstacles, design obstacles in order to achieve desired permutation of robots, and establish controlled interaction that is complex enough to allow arbitrary computations. In this video, we illustrate progress on all these challenges: we demonstrate NP-hardness of parallel navigation, we describe how to construct obstacles that allow arbitrary permutations, and we establish the necessary logic gates for performing arbitrary in-system computations.

  • Automatic Proofs for Formulae Enumerating Proper Polycubes  [+]
    Gill Barequet and Mira Shalah.

    Abstract: This video describes a general framework for computing formulae enumerating polycubes of size n which are proper in n−k dimensions (i.e., spanning all n-k dimensions), for a fixed value of k. (Such formulae are central in the literature of statistical physics in the study of percolation processes and collapse of branched polymers.) The implemented software already re-affirmed the already-proven formulae for k <= 3, and proved rigorously, for the first time, the formula enumerating polycubes of size n that are proper in n-4 dimensions.

  • Visualizing Sparse Filtrations  [+]
    Nicholas Cavanna, Mahmoodreza Jahanseir, and Donald Sheehy.

    Abstract: Over the last few years, there have been several approaches to building sparser complexes that still give good approximations to the persistent homology. In this video, we have illustrated a geometric perspective on sparse filtrations that leads to simpler proofs, more general theorems, and a more visual explanation. We hope that as these techniques become easier to understand, they will also become easier to use.

  • Visualizing Quickest Visibility Maps  [+]
    Topi Talvitie.

    Abstract: Consider the following modification to the shortest path query problem in polygonal domains: instead of finding shortest path to a query point q, we find the shortest path to any point that sees q. We present an interactive visualization applet visualizing these quickest visibility paths. The applet also visualizes quickest visibility maps, that is the subdivision of the domain into cells by the quickest visibility path structure.


Webpage: http://www.computational-geometry.org/SoCG-videos/socg15video/