26th Multimedia Exposition in
Computational Geometry

Like in previous years, the multimedia exposition in computational geometry is distributed on the web only. The videos are available in this page, with additional information linking to the authors' webpages.
Together with the vidoes, each submissions has an accompanying paper. The paper is hosted on the LIPIcs-Server. The papers appeared in the Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), and are available through the LIPIcs online proceedings.

Multimedia Contributions

• Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost
  Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, and An Nguyen
  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.
  mp4 (58 Mb)
• Ruler of the Plane
  Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, and Willem Sonke
  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.
  Intro (mp4) (21 Mb) — Play online
• Folding Free-Space Diagrams
  Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, and Taichi Shiitada
  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.
  mp4 (180 Mb)
• Cardiac Trabeculae Segmentation, an Application of Computational Topology
  Chao Chen, Dimitris Metaxas, Yusu Wang, and Pengxiang Wu
  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.
  mp4 (50 Mb)
• MatchTheNet
  Michael Joswig, Georg Loho, Benjamin Lorenz, and Rico Raber
  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.
  Intro (mp4) (16 Mb) — Play online
• On balls in a Hilbert polygonal geometry
  Frank Nielsen and Laëtitia Shao
  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.
  Intro (mp4) (17 Mb) — Download files from the author's site (includes an executable .jar file)

Recommended Video Player

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

Credits

These presentations were selected by the following multimedia program 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

---

26th Multimedia Exposition in Computational Geometry CG Week 2017