Workshop "Combinatorial Reconfiguration in Discrete and Computational Geometry"

As a part of the research project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration" (head investigator: Takehiro Ito), we are going to organize Workshop "Combinatorial Reconfiguration in Discrete and Computational Geometry" via Zoom on August 30 (based on European Timezone).

A basic idea is to share fundamental concepts and recent trends of combinatorial reconfiguration problems that arise in discrete and computational geometry and identify future research directions. In discrete and computational geometry, metric and topological properties concerning flips and compatibility of several geometric structures have been discussed; theory and algorithms for reconfiguration in robotics and nanomanufacturing have been studied; several questions involving continuous deformations in topology have been investigated through the algorithmic lens. This workshop aims at the broad audience of discrete mathematics and theoretical computer science, who wish to learn and work on this active research area.

The program will be exclusively composed of invited talks. Each talk is planned to span one hour, including discussion.

List of Confirmed Invited Speakers

• Hsien-Chih Chang (Dartmouth College, USA)
• Sándor Fekete (Technische Universität Braunschweig, Germany)
• Dan Halperin (Tel Aviv University, Israel)
• Hugo Parlier (University of Luxembourg, Luxembourg)
• Rodrigo Silveira (Universitat Politècnica de Catalunya, Spain)
• Emo Welzl (ETH Zürich, Switzerland)

Program

Talk Titles and Abstracts

• Dan Halperin
  • Title: Geometric Reconfiguration and Assembly Planning
  • Abstract:
    In Geometric Reconfiguration we are given two distinct spatial configurations of the same set of objects, a start configuration and a target configuration, and we wish to plan a sequence of operations that will take the objects from start to target while obeying various constraints, and primarily avoiding collision between the objects.
    A variety of geometric reconfiguration problems have been studied in discrete and computational geometry. At the same time geometric reconfiguration has important and (typically more) involved occurrences in robotics and automation. The talk will start with a new perspective on one of the best studied geometric reconfiguration problems: moving unit discs in the plane by a single translation each. We look for the optimal placement of the target configuration so as to minimize some bounding region (e.g., enclosing disc) of the necessary workspace, namely a region that will contain all the paths of the objects from start to target. Then we will discuss the more complex and hierarchical problem of assembly planning, where objects move in particular rounds, and where special physical requirements often arise such as the need that every moving subset of objects will be connected. Finally, we will briefly touch on multi-robot motion coordination, which constitutes a fairly broad family of geometric reconfiguration problems.
• Emo Welzl
  • Title: Triangulation Flip Graphs of Planar Point Sets
  • Abstract:
    Full triangulations of a finite planar point set P are maximal straight-line embedded plane graphs on P. In partial triangulations some non-extreme points can be skipped. Flips are minimal changes in triangulations (edge flips, and point insertion and removal flips). They define an adjacency relation on the set of triangulations of P, giving rise to the flip graph of all (full or partial, resp.) triangulations of P. In the seventies Lawson showed that flip graphs are always connected. This was motivated by the search for algorithms computing optimal triangulations (w.r.t. to several criteria).
    We investigate the structure of flip graphs, with emphasis on their vertex-connectivity. We obtain similar bounds as they follow for regular triangulations from secondary polytopes via Balinski's Theorem.
    Joint work with Uli Wagner, IST Austria
• Hugo Parlier
  • Title: Curves, Surfaces and Intersection
  • Abstract:
    On closed surfaces of positive genus, through classical work of Dehn, isotopy classes of simple closed curves can be described using their intersection numbers with other curves. Now what if you want to describe all curves in a similar way? This talk will be on joint work with Binbin Xu about this question, and where we end up constructing and studying so-called k-equivalent curves. These are distinct curves that intersect all curves with k self-intersections the same number of times.
• Rodrigo Silveira
  • Title: Flips in Higher Order Delaunay Triangulations
  • Abstract:
    This talk will be about higher order Delaunay triangulations, with an emphasis on what is known about its flip graph. This family of triangulations was proposed to try to obtain a compromise between good triangle shape (represented by the Delaunay triangulation), and optimal triangulations with respect to additional (so-called data-dependent) criteria. A triangulation of a set S of n points in the plane is order-k Delaunay if for every triangle its circumcircle encloses at most k points of S.
    The flip graph of S has one vertex for each possible triangulation of S, and an edge connecting two vertices when the two corresponding triangulations can be transformed into each other by a flip (i.e., exchanging the diagonal of a convex quadrilateral by the other one). The flip graph is an essential structure in the study of triangulations, but until recently it had been barely studied for order-k Delaunay triangulations.
    In this talk I will introduce higher order Delaunay triangulations, review what is known about them, both from a practical and theoretical point of view, and then focus on recent results about its flip graph.
• Hsien-Chih Chang
  • Title: Morphing Planar Metrics
  • Abstract:
    Planar metrics are ubiquitous in computational geometry and algorithm designs. Efficient methods can be developed for problems at hand when the underlying metric is planar, often due to the non-crossing nature of shortest paths.
    When the input metric is given as a distance matrix between points on a common boundary, we can efficiently construct a planar graph that summarizes the metric, and solve our problem on the graph instead. However, we might want to update the matrix entries later on. What can we do if we don't want to recompute the graph from scratch?
    The main focus of the talk is a natural set of operations called electrical moves that morphs the planar metric. We will discuss the recent progress in the understanding of its close relationship to curve deformations and applications to distance-based optimization problems. In particular, we will present how to update the edge-weights of a planar distance emulator to reflect the changes in the distance matrix, without altering the structure of the emulator. The talk will be sprinkled with open problems for the curious to ponder.
• Sándor Fekete
  • Title: Coordinated Reconfiguration for Swarms of Objects
  • Abstract:
    How can we coordinate the motion of many robots, vehicles, aircraft, or people? If each mobile agent has a destination in mind, how can it find an efficient route that avoids collisions with other agents as they simultaneously move to their destinations? These basic questions arise in many application domains, such as ground swarm robotics, aerial swarm robotics, air traffic control, and vehicular traffic networks.
    While it is usually not too difficult to achieve overall reconfiguration in a sequential manner (in which objects move to their target destinations, one after the other), exploiting parallelism in a swarm of objects for minimizing overall reconfiguration time is typically much harder. In this talk, I will present a number of results related to these types of questions.

Organizer

• Yoshio Okamoto (The University of Electro-Communications, Japan)