# Invited Speakers

Kokichi Sugihara

Meiji University Distinguished Professor Emeritus, Tokyo, Japan

**Topic:** Family Tree of Impossible Objects Created by Optical Illusion

**Abstract:**

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

**ABSTRACT: **

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

**Abstract:**

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

**Abstract:**

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

**Abstract:**