Accepted Multimedia Presentations

All videos can be found at

  • Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, and An Nguyen
    Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost [+]
    We present results arising from the problem of sweeping a mosquito-infested area with an Un-manned Aerial Vehicle (UAV) equipped with an electrified metal grid. This is related to the Traveling Salesman Problem, the Lawn Mower Problem and, most closely, Milling with Turn Cost. Planning a good trajectory can be reduced to considering penalty and budget variants of covering a grid graph with minimum turn cost. On the theoretical side, we show the solution of a problem from The Open Problems Project that had been open for more than 15 years, and hint at approximation algorithms. On the practical side, we describe an exact method based on Integer Programming that is able to compute provably optimal instances with over 500 pixels. These solutions are actually used for practical trajectories, as demonstrated in the video.
  • Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, and Willem Sonke
    Ruler of the Plane [+]
    Ruler of the Plane is a set of games illustrating concepts from combinatorial and computational geometry. The games are based on the art gallery problem, ham-sandwich cuts, the Voronoi game, and geometric network connectivity problems like the Euclidean minimum spanning tree and traveling salesperson problem.
  • Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, and Taichi Shiitada
    Folding Free-Space Diagrams [+]
    By folding the free-space diagram for efficient preprocessing, we show that the Frechet distance between 1D curves can be computed in O(nk log n) time, assuming one curve has ply k.
  • Chao Chen, Dimitris Metaxas, Yusu Wang, and Pengxiang Wu
    Cardiac Trabeculae Segmentation, an Application of Computational Topology [+]
    In cardiac image analysis, it is important yet challenging to reconstruct the trabeculae, namely, fine muscle columns whose ends are attached to the ventricular walls. To extract these fine structures, traditional image segmentation methods are insufficient. We present how topological methods, including persistent homology and homology localization, can be used to extract high quality segmentation result.
  • Michael Joswig, Georg Loho, Benjamin Lorenz, and Rico Raber
    MatchTheNet [+]
    We present an interactive game which challenges a single player to match 3-dimensional polytopes to their planar nets. It is open source, and it runs in standard web browsers.
  • Frank Nielsen and Laëtitia Shao
    On balls in a Hilbert polygonal geometry [+]
    Hilbert geometry is a metric geometry that extends the hyperbolic Cayley-Klein geometry. In this video, we explain the shape of balls and their properties in a convex polygonal Hilbert geometry. First, we visualize the combinatorial properties of Hilbert balls, showing that the shapes of Hilbert polygonal balls depend both on the center location and on the complexity of the Hilbert domain but not on their radii. We give an explicit description of the Hilbert ball for any given center and radius. We then illustrate the intersection of two Hilbert balls. In particular, we consider the cases of empty intersection and internal/external tangencies.

Multimedia Exposition

Multimedia presentations are sought for the 26th International Computational Geometry Multimedia Exposition (CG:MME), which will take place in July as part of Computational Geometry Week 2017. Computational Geometry Week also encompasses the 33rd 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 Requirements

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, should be avoided, as well as speakers with too heavy accent.

Interactive applications (e.g., HTML5, Flash, AIR, Java, executable files, etc.) should provide a “demo” video demonstrating the functionalities of the software, for archiving on the website. These videos can be created with any screen recording software (such as CamStudio/VideoPad for Windows, QuickTime/iMovie for Mac, or Kazam/Kdenlive for GNU/Linux) together with voice description (by the authors or by a speech generator, such as eSpeak).

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

It is strongly encouraged to contact the CG:MME program committee 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.


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.

The application itself should be submitted with a small “how-to” use documentation in plain text. Ideally, the application should be universal (be able to run on any device and OS), but it is ok as long as it runs in reasonably common setups (for example, desktop computers with windows and Mac OS). We also recommend adding a “makefile” or a similar file to ease compilation.

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 and the lipics.cls LaTeX style file at

Send a mail to the CG:MM chair, Matias Korman (mati at by March 10, 2017, 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 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.

Important Dates

March 10, 2017: Multimedia submissions due
March 24, 2017: Notification of acceptance/rejection
April 7, 2017: Final version of written abstracts due
May 19, 2017: Final versions of multimedia content due
July 4-7, 2017: CGWeek 2017

All deadlines are 23:59 anywhere on earth.

Multimedia Committee

Matias Korman (chair), Tohoku University, Japan
Yoshio Okamoto, University of Electro-Communications, Japan
Alexander Pilz, ETH Zürich, Switzerland
Rodrigo I. Silveira, Universitat Politècnica de Catalunya, Spain
Darren Strash, Colgate University, USA
Kevin Verbeek, TU Eindhoven, the Netherlands
Sander Verdonschot, University of Ottawa, Canada