Invited Speakers

Kokichi Sugihara
Meiji University Distinguished Professor Emeritus, Tokyo, Japan

Topic: Family Tree of Impossible Objects Created by Optical Illusion

We classify a family of “impossible objects” that are real physical objects but appear to be impossible due to optical illusion, and tries to organize them into a family tree according to the reasons why they look impossible. There are two fundamental sources of ambiguity in reconstructing 3D objects from 2D images. One is the lack of depth information in images; there are infinitely many 3D shapes. The other is the freedom in the choice of the viewpoint; the perceived object changes when we change the viewpoint. The proposed family tree will give a new framework to start further researches on impossible objects and 3D optical illusion

János Pach
Rényi Institute of Mathematics, Budapest, Hungary

Topic : Crossing Parallels

According to the crossing lemma of Ajtai, Chvatal, Newborn, Szemeredi and Leighton (1981), the crossing number of any graph with n vertices and e edges is at least ce^3/n^2 , where c is an absolute constant. This result, which is tight up to the constant factor, has been successfully applied to a variety of problems in discrete and computational geometry, additive number theory, algebra, and elsewhere. The lemma easily extends to multigraphs: if the multiplicity of every edge is at most $m$, then the crossing number of the graph is at least ce^3/(mn^2) . However, much better bounds can be established for multigraphs in which no two parallel edges are homotopic.The latest results are joint with Fox and Suk.

Erik Demaine
Massachusetts Institute of Technology, USA

Topic: Understanding the Complexity of Motion Planning through Gadgets

Most motion planning problems -- designing the route for one or more agents (robots, humans, cars, drones, etc.) through a changeable environment -- are computationally difficult: NP-hard, PSPACE-hard, or worse. Such hardness proofs usually consist of several gadgets -- local pieces of environment with limited agent interactions/traversals, some of which change local state, which in turn change available interactions/traversals -- that can be pasted together into the overall reduction. In this talk, I'll describe our quest to characterize exactly which such gadgets suffice to prove different kinds of hardness, in our motion-planning-through-gadgets framework that has developed over the past few years. This theory enables many hardness proofs, old and new, to be distilled down to a single diagram of a single gadget.

Stefan Langerman
Algorithms Research Group, Université Libre de Bruxelles, Belgium

Topic: Towards Dynamic Voronoi Diagrams

Voronoi Diagrams for a set P of points in the plane associate to
each point q in P the region of the plane that is closer to q
than to any other point of P.
Together with their dual, Delaunay Graphs, they are some
of the most relevant structures used to understand the distance or
proximity for sets of points. Now what happens when the set P is modified?

It turns out Voronoi Diagrams are remarkably fragile, and the
addition, deletion or perturbation of a single point can
sometimes change a constant fraction of its features.
This makes the goal of efficiently maintaining Voronoi Diagrams as
point sets change or move, seemingly unattainable. But is it?

Jittat Fakcharoenphol
Theory Research Group, CPE, Kasetsart University, Thailand

Topic: Approximation schemes for geometric NP-hard problems: geometry meets algorithms

In computer science, numerous optimization problems are NP-hard; thus, it is unlikely to find efficient algorithms for solving them exactly. However, many problems have natural instances on Euclidean planes, for example the Travelling Salesman Problem, the Minimum Steiner Tree Problem, covering problems in geometric graphs, and many clustering problems. Geometry gives structures to these instances, allowing computer scientists to devise efficient approximation schemes that find (1 +epsilon)-approximate solutions in polynomial time for any constant epsilon > 0. In this survey, we outline many important ideas used in those algorithms, including dynamic programming and randomization.

Daniel Horsley
Monash University, Australia

Topic: Decomposing complete multigraphs into stars of varying sizes

An edge decomposition of a multigraph G is a set of subgraphs of G$such that each edge of G occurs in precisely one of the subgraphs. In 1979 Tarsi showed that an edge decomposition of a complete multigraph into stars of size k exists whenever the obvious necessary conditions hold. In 1992 Lonc gave necessary and sufficient conditions for the existence of an edge decomposition of a (simple) complete graph into stars of sizes m1… ,mt. I will discuss the common generalisation of these problems: when does a complete multigraph admit an edge decomposition into stars of sizes m1… ,mt? This problem exhibits more complicated and interesting behaviour than either of its specialisations. It turns out that the general problem is NP-complete, but that it becomes tractable if we place a strong enough upper bound on max(m1… ,mt). We are able to determine the upper bound at which this transition occurs. The basis of this result is a characterisation of when an arbitrary multigraph can be decomposed into stars of sizes m1… ,mt with specified centres, which extends a result of Hoffman. A generalisation of Landau’s theorem on tournaments also follows from this characterisation. This is joint work with Rosalind Cameron (University of Canterbury).