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.
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.
Video (mp4, 58 Mb) | Youtube link
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.
Watch intro (mp4, 21 Mb) | Youtube link
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.
Video (mp4, 180 Mb) | Youtube link
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.
Video (mp4, 50 Mb) | Youtube link
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.
Watch intro (mp4, 16 Mb)
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.
Watch intro (mp4, 17 Mb) | Youtube link
Download extra files from the author's site (file includes an executable .jar file)
Recommended Video PlayerVLC (available for Windows, Mac, Linux, and other operating systems) can play all of this year's video submissions.
CreditsThese 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