- Sergio Cabello (University of Ljubljana)
- Erik Demaine (Massachusetts Institute of Technology)
- Tamal Dey (The Ohio State University)
- Dan Halperin (Tel Aviv University)
- Marc van Kreveld (Utrecht University)
This activity will consist of 1-2 lectures per day, focusing on open problems on different topics, in relation to the subjects of Advanced Course I. The remaining of the day, attendees will have plenty of time to work and interacting with each other.
Sergio Cabello: Graph algorithms and computational geometry
We will discuss some of the interactions between graph algorithms and computational geometry. I will present some efficient algorithms for geometric intersection graphs that use tools from computational geometry. I will also explain some examples where insights from computational geometry play an important role in the design of graph algorithms.
Erik Demaine: Geometric Folding Algorithms: Linkages, Origami, Polyhedra
What forms of origami can be designed automatically by algorithms? How might we build reconfigurable robots like Transformers or Terminator 3, hinging together a collection of pieces that dynamically reconfigure into arbitrary shapes? When can a robotic arm of rigid rods be folded into a desired configuration? What shapes can result by folding a piece of paper flat and making one complete straight cut? What 3D surfaces can be manufactured from a single sheet of material? How might proteins fold?
Geometric folding is a branch of discrete and computational geometry that addresses these and many other intriguing questions. I will give a taste of the many results that have been proved in the past several years, as well as the several exciting unsolved problems that remain open. Many folding problems have applications in areas including manufacturing, robotics, graphics, and protein folding.
Tamal Dey: Computational Topology and Data Analysis
Many applications involving shapes and data not only require analyzing and processing their geometries, but also associated topologies. In the past two decades, computational topology, an area rekindled by computational geometry has emphasized processing and exploiting topological structures of shapes and data. The understanding of topological structures in the context of computations has resulted into sound algorithms and has also put a thrust in developing further synergy between mathematics and computations in general. This talk aims to delineate this perspective by considering some of the recent developments in topological data analysis including
(i) sparsification of data
(ii) mapper methodology
(iii) optimal homology cycle computations, and
(iv) discrete Morse theory.
For each of the covered topics, we will give the necessary backgrounds in topology, state some of the key results, and indicate open questions/problems. The hope is that the talk will further stimulate the interest in tying together topology with computation.
Dan Halperin: Movable Separability and Robotic Assembly Planning
Over thirty years ago Godfried Toussaint published a collection of computational-geometry problems under the title “movable separability of sets”, pertaining to separating ensembles of objects into individual parts by continuously moving some objects relative to the rest without collision. Since then the set of problems have grown, the solution techniques have significantly developed, and the applications where such problems arise have become ever more varied. In my talk I will review basic problems in this area, describe old and new application domains of movable-separability with an emphasis on assembly planning, survey methods to attack such problems in theory and practice, and portray a few current challenges.
Marc Van Kreveld: Geometric Puzzles: novelties and automated generation
There are many puzzles in the world, both physical and digital ones. From the algorithms research perspective, a lot of attention has been given to combinatorial and graph-based puzzles and how to solve them. We will focus on puzzles with a geometric component and where techniques from discrete and computational geometry can be employed to generate them. Automated generation of puzzles is arguably more useful than automated solving. We will see new connect-the-dots puzzles, new nonogram puzzles, new graph planarization puzzles, and the app game called Lines!
There will be one lecture every morning, 2h long. After that, attendees and lecturers will work together in open problems.
Monday, April 23
Tuesday, April 24
Wednesday, April 25
Thursday, April 26
Friday, April 27
Note: Afternoon seminars will be announced in-place.