Advanced Course I: Advanced Techniques for Algorithmic Geometry (April 16-20, 2018)
This course will survey some of the most recent algorithmic paradigms and data structures that have led to the latest advances in the state of the art of computational geometry. There will be
Erin W. Chambers: Some Recent Trends in Computational Topology
Computational topology is an emerging area which is growing from the increasing need for algorithms that are rooted in the tools and techniques of topology; it has proven useful for a variety of areas such as data analysis, mesh reconstruction, biological modeling, and GIS analysis. The two primary tools for algorithms in computational topology are homotopy and homology, both of which capture topological invariants of the shape, such as the number of handles or voids, rather than focusing on the geometry of the structure. While homotopy is a more complete invariant of the shape, it is also much harder to compute, and hence there is a large body of work that relies on the coarser invariant of homology. In this course, I will introduce these fundamental concepts and then cover a few recent trends in more depth, including: algorithms to compute persistent homology of a point set or simplicial complex; the crust algorithm and its descendants for surface reconstruction; algorithms on surface embedded graphs for fundamental combinatorial problems such as flows and cuts; and algorithms to compute similarity measures for curves and surfaces.
Nabil Mustafa: Local Search in Geometry: Samples, Separators and Subdivisions
Local-search is an intuitive approach towards solving optimization problems: start with any feasible solution, and try to improve it by local operations. Like other greedy approaches, it can fail to find the global optimum by getting stuck on a locally optimal solution; in fact, for purely graph-theoretic problems it is often easy to construct instances where local search algorithms fail to find even approximately good solutions.
A key realization in the last several years has been the effectiveness of local search for geometric problems, leading to the resolution of a series of long-standing open computational geometry problems. The underlying reason for effectiveness of local search in geometric problems is the existence and interplay between three compact structures: separators, random samples, and spatial subdivisions.
In this course, I will present the ideas and techniques behind the use of local-search in the design of provably good approximation algorithms for three types of geometric problems: combinatorial (e.g., geometric independent set, geometric set cover and hitting set), Euclidean (the very recent breakthroughs in algorithms for k-means, k-median) and metric.
Lecture 1. The basic tools: Separators, Sampling and Subdivisions
Lecture 2. Combinatorial Local Search
Lecture 3. Euclidean Local Search
Lecture 4. Metric Local Search
Lecture 5: Other recent breakthroughs in geometric combinatorial optimization
There will be two lecture sessions every morning, respectively 2h and 1h 30min long. In the afternoons, attendees and lecturers will work in open problems.
Inspiring Lectures I: Computational Geometry Towards Applications (April 23-27, 2018)
- 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!
Hands-on course on Geometric Software (April 30 – May 4, 2018)
- Andreas Fabri and Sébastien Loriot (CGAL, Geometry Factory)
- Nicolai Hähnle (OpenGL, AMD)
- Michael Joswig (Polymake, TU Berlin)
- Zoltán Kovács (GeoGebra, Johannes Kepler Universität)
This activity is intended to provide practical knowledge about important software tools relevant to researchers dealing with geometric problems. It will include lectures as well as practicum.
Contents and organization
Monday, April 30. Andreas Fabri & Sébastien Loriot – CGAL: The Computational Geometry Algorithms Library, by Example
Requirements: In order to be productive you should have installed the latest release of CGAL, either on Linux or Windows together with its dependencies.
CGAL is an open source project that provides a library of geometric data structures and algorithms. The course consists of three sessions in the morning and programming exercises in the afternoon. In the first 30min session you learn how the CGAL project evolved, how it is organized, how researchers can potentially contribute, what the license is, etc. The second and third 60min session cover two topics in depth, namely:
- Polygon Mesh: Processing mesh simplification, remeshing, skeletonization, segmentation, Boolean operations, hole filling, slicing, AABB tree, etc.
- Mesh Generation: Surface and tetrahedral volume mesh generation for input coming from voxel data, implicit functions, polyhedral surfaces, Nurbs patches. Periodic mesh generation.
In these sessions we switch between life demos so that you see what the algorithms are about, give the intuition of the underlying theory, and explain the principles of the API. In the afternoon you develop software using CGAL. Ideally you identify a CGAL package that might be helpful in your own research, and you start playing around with it. You most probably start from the examples provided for the CGAL package you are interested in. During this session we look over your shoulder, give hints how to quickly find information in the manuals.
Tuesday, May 1. Bank holiday
Wednesday, May 2. Nicolai Hähnle – OpenGL
Thursday, May 3. Michael Joswig – Polyhedral Computations with polymake
Requirements: Attendees should bring their laptops. They should read and follow the technical advice at http://page.math.tu-berlin.de/~joswig/software/polymake/DCCG2018/index.html
We will start with an introduction to computations in high-dimensional polyhedral geometry, with applications to, e.g., optimization and tropical geometry. Then we will review several algorithms for computing convex hulls and survey their advantages and disadvantages by analyzing explicit examples. The course will end with some reports about the current frontiers of polyhedral computation.
Friday, May 4. Zoltán Kovács – Modeling computational geometry with GeoGebra
Requirements: Attendees should bring their laptops.
Advanced Course II: New Results in Combinatorial & Discrete Geometry (May 7-11, 2018)
- Bojan Mohar (Simon Fraser University & University of Ljubljana)
- Gelasio Salazar (Univ. Autónoma San Luis Potosí)
This course will cover hot topics in combinatorial and discrete geometry, focusing on a selection of techniques that have enabled some of the latest breakthroughs in the area. The activity will consist of two lectures every morning, each at most 2h long, followed by work and interacting in the afternoons.
Bojan Mohar: Graphs on surfaces
The course will outline fundamental results about graphs embedded in surfaces. It will briefly touch on obstructions (minimal non-embeddable graphs), separators and geometric representations (circle packing). Time permitting, some applications will be outlined concerning homotopy or homology classification of cycles, crossing numbers and Laplacian eigenvalues.
Gelasio Salazar: Crossing numbers and related topics in combinatorial topology and geometry
The crossing number is an intriguing entity. Unlike most graph-theoretical parameters, we do not even know its value for the usual suspects: complete graphs and complete bipartite graphs. The rich history of this parameter goes back to the renowned combinatorialist and number theorist Paul Turán, and to British artist Anthony Hill, a remarkable figure of the Constructivist Group. Determining the exact crossing number of familiar collections of graphs remains a stubbornly open problem, and perhaps for this reason most early research on crossing numbers focused on evaluating this parameter for specific families of graphs, or even for a single graph. Among the few notable early-ish exceptions we have the Crossing Lemma, whose proof(s), and applications we will cover in this course. In the last twenty years or so, the field has become a mainstream part of Topological Graph Theory, due to several important theorems of a structural character. Quite a few important questions on crossing numbers remain open to (elementary? intricate?) ideas from newcomers to the field. We will survey a biased selection of what is known about this parameter, from its early history back to Turán, Zarankiewicz, and Hill, up to the most recent developements, with a strong emphasis on open questions. A selected collection of related problems and results in combinatorial geometry and topology will also be covered. Our plan is to highlight how tools from algebraic, probabilistic, and pure combinatorics shed light on an eminently topological problem for which, at some basic level, the only topological tool available is the Jordan curve theorem.
Inspiring Lectures II: Challenges in Combinatorial & Discrete Geometry (May 14-18, 2018)
- Karim Adiprasito (Hebrew University of Jerusalem & University of Leipzig)
- Imre Bárány (Hungarian Academy of Sciences & University College London)
- Alexander Barvinok (University of Michigan)
- Vida Dujmović (University of Ottawa)
- Fabrizio Frati (Università Roma Tre)
- Adam Sheffer (California Institute of Technology)
- Csaba D. Tóth (California State University Northridge)
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 II. The remaining of the day, attendees will have plenty of time to work and interacting with each other.
Karim Adiprasito: Title: The toric toolkit
I will present algebraic tools borrowed from toric geometry, focused on applications towards extremal problems in geometric combinatorics. The presentation will not require any knowledge of algebraic geometry.
Imre Bárány: Vector-sum theorems, their relatives and applications
About hundred years ago, answering a question of Riemann, Steinitz proved the following result. Let B be the unit ball of the Euclidean norm in R d and assume that V⊂B is finite and the sum of the elements in V is zero. Then there is an ordering v1,…,vn of the vectors in V such that all partial sums along this ordering have norm smaller than 2d. I am going to talk about extensions, generalizations, and applications of this remarkable theorem.
Alexander Barvinok: Computational complexity and complex geometry
I will discuss a general principle: if a combinatorially defined polynomial (such as the permanent of a matrix or the independence polynomial of a graph) has no zeros in a certain complex domain, then it can be efficiently computed (approximated) in a slightly smaller domain. On one hand, this leads to a number of efficient approximation algorithms in various problems of combinatorial counting and, on the other hand, to a number of deceptively simple looking problems of combinatorial geometry.
Vida Dujmović: Layered separators/treewidth and their applications
Graph separators are a ubiquitous tool in graph theory and computer science. However, in some applications, their usefulness is limited by the fact that the separator size depends on the size of the graph. This is the case for planar graphs, and more generally, for proper minor-closed families which can have Omega(sqrt n) separators in graphs with n vertices.
I will talk about a special type of graph separator, called a “layered separator” and the closely-related notion of layered treewidth. These separators may have linear size in n, but have bounded size with respect to a different measure, called width. Planar graphs, graphs of bounded Euler genus, and k-planar graphs admit layered separators of bounded width. I show how (with simple proofs) they can be used to obtain logarithmic bounds for a variety of applications for which O(sqrt n) was the best known long-standing bound. These applications include, track layouts, queue layouts, stack layouts, nonrepetitive graph colourings and 3-dimensional grid drawings of graphs.
Fabrizio Frati: Morphing geometric representations of graphs
In this talk I will survey the state of the art on morphing geometric representations of graphs. Suppose that one is given two topologically-equivalent geometric representations of a graph. Can one representation be continuously transformed into the other one while preserving the graph topology during the transformation? This question has been studied for more than a century and yet answering it completely is still an elusive goal. The study of morphs of graph representations has proved to be intertwined with several areas of mathematics and computer science. I will talk about some of the most natural versions of the above question, related to morphing planar representations, non-planar representations, and three-dimensional representations. I will present the main methodologies currently used in this field, as well as a large number of open problems at various levels of difficulty.
Adam Sheffer: Using Additive Combinatorics in Combinatorial Geometry
Additive Combinatorics is an active research field combining combinatorics, number theory, and harmonic analysis. In recent years, a variety of results in Combinatorial Geometry have been obtained by using ideas from Additive Combinatorics. For example, the concept of additive energy turned out to be very useful for several types of geometric problems. In this talk we will introduce basic concepts from Additive Combinatorics, and then show how these are used to derive geometric results. No prior knowledge of the subject is necessary. The talk will also go over related natural problems that were not seriously studied yet (since these problems originate from very recent works). Moreover, there are likely to be various additional Combinatorial Geometry problems that can be studied using similar tools from Additive Combinatorics. This makes this topic well suited for collaborations without requiring a large amount of background.
Csaba Tóth: Transition Operations over Plane Graphs
Let S be a finite set of points in general position in the plane, and G(S) a family of planar straight-line graphs with vertex set S (such as noncrossing matching, spanning trees, spanning cycles, triangulations). Combinatorial properties of G(S) are often rely on operations (moves) that transform one graph in G(S) into another by replacing some edges; such as edge exchange, edge flip, edge rotation, and edge slide (either as elementary moves that modify a constant number of edges, or simultaneous operations that perform one or more elementary moves simultaneously). In a transition graph, the vertices represent the graphs in G(S), and adjacency represents a valid transformation. This talk will review recent results on the extremal properties of transition graphs and pose open problems.
Working and interacting week (May 22-25, 2018)
Week devoted to research collaborations between participants. The only activity scheduled for this week will be the seminar talks.
A research workshop organized within the H2020 project CONNECT (COmbinatorics of NEtworks and CompuTation). This event is open to all IRP participants. Please see the CONNECT-GAAN web page for registration and further details.
This series of workshops started in 2014, promoted by Oswin Aichholzer, Ferran Hurtado and Jorge Urrutia, under the auspice of the EuroGIGA ComPoSe project. The workshop intends to bring together a group of 20-25 researchers to work together on open problems brought by the organizers and the participants. Attendance to the workshop is by invitation, but a number of places have been reserved for IRP participants interested in taking part. Please check the 5th AJMS web page, and contact the workshop organizers if you would like to participate.
During the whole duration of the program we will hold a regular weekly seminar in which other visitors will be able to present recent results on the topics of the program. The frequency of the seminar will depend on the number of visitors, but we expect to have at least one and at most two talks per week. These seminars will be open to the whole Mathematics community.
In addition, all students participating in the program will be invited to give a talk about their current work in a student seminar that will take place regularly in the afternoons during the five central weeks of the program. The frequency of the talks will depend on the number of students, but we expect to have at most two talks per day. Other visitors, including students and also more senior researchers will be encouraged to attend.