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: