Home » **Seminar**

## TAU's Seminar on Computational Geometry and Robotics

Wednesdays at 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)

Zoom: Request the link from Dan Halperin

##
Item#1

##
Item#2

##
02.11.22, Micha Sharir, Tel Aviv University: Recent Advances in Geometric Optimization

**Wednesday, November 2nd, 4:10pm Tel Aviv time (3:10pm CET)**

**Abstract:**

We resurrect, extend and generalize a technique, developed 7 years ago for a Frechet distance problem,

and show that it can solve a large collection of geometric optimization problems, significantly improving known solutions,

for example for the reverse shortest path problem on unit-disk graphs, and obtaining new and fast solutions to other problems.

The technique is a simpler alternative to (or variant of) parametric search, for problems where the decision procedure is hard to

parallelize. The new algorithms make effective use of, and develop further, semi-algebraic range searching, a central topic in

geometry, where efficient implementations of the technique have emerged only very recently.

Joint work with Pankaj Agarwal and Matya Katz

##
09.11.22, Mauro Salazar, Eindhoven University of Technology Optimization Models and Methods for Cyber-socio-technical Systems: From Electric Racing to Sustainable Urban Mobility

**Wednesday, November 9th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**Nowadays mobility is facing challenges ranging from urban traffic to environmental pollution and noise. The advent of new cyber-physical technologies such as autonomous driving, wireless communications and powertrain electrification might provide us with promising opportunities to face these challenges. Yet how to successfully combine such technologies in order to design and deploy economically-viable, socially-inclusive and environmentally-friendly mobility solutions is still unclear.

In this context, this talk will show how we devised optimization models and methods for research projects ranging from the single-vehicle level to the transportation-system level. In particular, I will first present models and optimization algorithms to design and control fully-electric endurance race cars via convex optimization. Second, I will give an overview on our work on Intermodal Autonomous Mobility-on-Demand—namely, a mobility system whereby self-driving cars provide on-demand mobility jointly with public transit and active modes—including optimization models to analyse the societal benefits stemming from these new mobility paradigms, design methods, and incentive schemes to align the behavior of selfish users with the system optimum whilst guaranteeing fairness.

Mauro Salazar is an Assistant Professor in the Control Systems Technology section at Eindhoven University of Technology (TU/e), The Netherlands, with a co-affiliation at Eindhoven AI Systems Institute (EAISI). He received the PhD degree in Mechanical Engineering from ETH Zürich in collaboration with the Ferrari Formula 1 team in 2019, and then moved to Stanford University for his Postdoc until 2020. Mauro’s research is focused on optimization models and methods for cyber-socio-technical systems and control, with applications on sustainable and human-centered mobility, pandemics, and material design. He was awarded the ETH Medal for his MSc and PhD theses, and his papers were recognized with the Best Student Paper award at the 2018 IEEE Intelligent Transportation Systems Conference and at the 2022 European Control Conference. In 2022, he was nominated for TU/e’s Young Researcher Award.

##
23.11.22, Jana Tumova, KTH Royal Institute of Technology: Formal Methods for Planning With Spatial Constraints

**Wednesday, November 23rd, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**As autonomous robots move from enclosed environment to our everyday lives, we have to ask: How can we ensure that they work as expected and how can we even specify what it means to work as expected? Formal methods have proven to be useful in addressing these questions; temporal logics provide rich, rigorous, yet user-friendly specification formalism and formal synthesis offers a way to automatically generate a plan or a controller that provably satisfies the specification (or satisfies it to some guaranteed extent).

In this talk, we will focus on specification of spatial constraints for motion planning in Signal Temporal Logic (STL). We will discuss quantitative semantics of STL to distinguish between more and less compliant motion plans, and present an RRT*-based motion planning algorithm that converges to the maximally satisfying plan. Then, we will look into shorter-horizon control problems with spatial constraints, such as unparking from a tight parking spot. We will discuss how to combine a construction of a library of feedback motion primitives and an over- and under-approximation of the collision space to either find a desired motion plan, prove path non-existence, or trigger refinement of the primitives and the collision space approximations.

##
30.11.22, Jingjin Yu, Rutgers University: Rubik Tables, Stack Rearrangement, and Multi-Robot Routing

**Wednesday, November 30th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**In a basic Rubik table problem, there are $n$ item types, each with a multiplicity of $n$. These $n^2$ items are randomly placed in an $n x n$ table, one in each cell. In a shuffle, a row (resp., column) of the table may be permuted to achieve an arbitrary configuration of the items in that row (resp., column). We ask how many shuffles are needed to sort the table so that type $i$ items occupy column $i$ of the table. Somewhat surprisingly, $2n$ shuffles suffice. Rubik tables and its many generalizations enable the successful tackling of difficult “sequential combinatorial optimization” problems in robotics, including stack rearrangement and multi-robot path planning, resulting in polynomial time algorithms for computing asymptotically optimal solutions that were previously not possible, to our knowledge. In particular, using the Rubik table abstraction as a building block, we are able to achieve $1.x$ asymptotic makespan optimality for multi-robot path planning on grids in polynomial time, with high probability.

##
07.12.22, Mikkel Abrahamsen, University of Copenhagen: Covering Polygons is Even Harder

**Wednesday, December 7th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**In the MINIMUM CONVEX COVER (MCC) problem, we are given a simple polygon P and an integer k, and the question is if there exist k convex polygons whose union is P. It is known that MCC is 𝖭𝖯-hard and in ∃ℝ. We prove that MCC is ∃ℝ-hard, and the problem is thus ∃ℝ-complete. In other words, the problem is equivalent to deciding whether a system of polynomial equations and inequalities with integer coefficients has a real solution.

If a cover for our constructed polygon exists, then so does a cover consisting entirely of triangles. As a byproduct, we therefore also establish that it is ∃ℝ-complete to decide whether k triangles cover a given polygon.

The issue that it was not known if finding a minimum cover is in 𝖭𝖯 has repeatedly been raised in the literature, and it was mentioned as a “long-standing open question” already in 2001. We prove that assuming the widespread belief that 𝖭𝖯≠∃ℝ, the problem is not in 𝖭𝖯.

An implication of the result is that many natural approaches to finding small covers are bound to give suboptimal solutions in some cases, since irrational coordinates of arbitrarily high algebraic degree can be needed for the corners of the pieces in an optimal solution.

##
14.12.22, David Mount, University of Maryland: Economical Convex Coverings and Applications

**Wednesday, December 14th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Given a convex body K and epsilon > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an epsilon expansion of K.

It is known how to construct coverings of size n^{O(n)}/epsilon^{(n-1)/2} for general convex bodies in R^n. In special cases, such as when the convex body is the Lp unit ball, this bound has been improved to 2^{O(n)}/epsilon^{(n-1)/2}. In this talk, I will present results of an upcoming paper in SODA 2023, where we show that such an improvement holds for arbitrary convex bodies.

I will also discuss applications of these results to other problems in convex approximation, including convex approximations in the Banach-Mazur metric, and approximation algorithms for the closest-vector problem and integer programming.

(This work will be presented at SODA 2023. Joint work with Sunil Arya and Guilherme da Fonseca.)

##
21.12.22, Gil Kalai, Hebrew University: Around Borsuk's Covering Problem

**Wednesday, December 21st, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**Borsuk asked in 1933 if every set of diameter one in Euclidean d-space can

be covered by d + 1 sets of smaller diameter. In 1993, a negative solution,

based on a theorem by Frankl and Wilson, was given by Kahn and the

speaker. In the lecture I will present various questions and results related

to Borsuk’s covering problem.

Home page: https://ma.huji.ac.il/~kalai/

##
28.12.22, **No seminar**

**No seminar**

##
04.01.23, Sven Koenig, University of Southern California (USC): Multi-Agent Path Finding and Its Applications

##
11.01.23, Evanthia Papadopoulou, Università della Svizzera italiana: Voronoi-Like Graphs – Towards Simple Linear Time Algorithms for Voronoi Trees and Forests

**Wednesday, January 11th, 4:10pm Tel Aviv time (3:10 pm CET, 9:10am NY time)**

**Evanthia Papadopoulou, Università della Svizzera italiana**

**Abstract:**

diagrams of segments, circles, polygons, or clusters of points in the

plane, are sometimes overlooked or underestimated. As a result some

basic questions concerning the latter diagrams may surprisingly remain

open to date. In this talk I will discuss Voronoi-like graphs as a tool

towards addressing such problems.

A Voronoi-like graph is a relaxed Voronoi structure, defined as a graph

on the arrangement of a given bisector system. In a Voronoi-like graph,

a vertex v and its incident edges, within a small neighborhood around v,

must appear in a Voronoi diagram of three sites. For points in the

Euclidean plane, where the bisector system forms a line arrangement, a

Voronoi-like graph always coincides with the Voronoi diagram of the

involved sites. How about bisector systems which are not lines (nor

pseudolines), such as those related to line-segments, or more generally,

to abstract Voronoi diagrams? I will answer this question in this talk

and give examples of simple expected linear-time algorithms to compute

Voronoi-like trees (or forests). Examples include updating an abstract

Voronoi diagram after deletion of one site, updating a constraint

Delaunay triangulation after inserting a new segment constraint, and

others. As a byproduct, I will also discuss a simple alternative to

backwards analysis applicable to order-dependent structures.

Some parts of this talk is joint work with Kolja Junginger.

##
18.01.23, Russ Tedrake, MIT and Toyota Research Institute: Motion Planning Around Obstacles with Convex Optimization

**Wednesday, January 18th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**

In this talk, I’ll describe a new approach to planning that strongly leverages both continuous and discrete/combinatorial optimization. The framework is fairly general, but I will focus on a particular application of the framework to planning continuous curves around obstacles. Traditionally, these sort of motion planning problems have either been solved by trajectory optimization approaches, which suffer with local minima in the presence of obstacles, or by sampling-based motion planning algorithms, which can struggle with derivative constraints and in very high dimensions. In the proposed framework, called Graph of Convex Sets (GCS), we can recast the trajectory optimization problem over a parametric class of continuous curves into a problem combining convex optimization formulations for graph search and for motion planning. The result is a non-convex optimization problem whose convex relaxation is very tight — to the point that we can very often solve very complex motion planning problems to global optimality using the convex relaxation plus a cheap rounding strategy. I will describe numerical experiments of GCS applied to a quadrotor flying through buildings and robotic arms moving through confined spaces. On a seven-degree-of-freedom manipulator, GCS can outperform widely-used sampling-based planners by finding higher-quality trajectories in less time, and in 14 dimensions (or more) it can solve problems to global optimality which are hard to approach with sampling-based techniques.

**Bio:**

Russ Tedrake is the Toyota Professor at the Massachusetts Institute of Technology (MIT) in the Department of Electrical Engineering and Computer Science, Mechanical Engineering, and Aero/Astro, and he is a member of MIT’s Computer Science and Artificial Intelligence Lab (CSAIL). He is also the Vice President of Robotics Research at Toyota Research Institute (TRI). He received a B.S.E. in Computer Engineering from the University of Michigan in 1999, and a Ph.D. in Electrical Engineering and Computer Science from MIT in 2004. Dr. Tedrake is the Director of the MIT CSAIL Center for Robotics and was the leader of MIT’s entry in the DARPA Robotics Challenge. He is a recipient of the NSF CAREER Award, the MIT Jerome Saltzer Award for undergraduate teaching, the DARPA Young Faculty Award in Mathematics, the 2012 Ruth and Joel Spira Teaching Award, and was named a Microsoft Research New Faculty Fellow. His research has been recognized with numerous conference best paper awards, including ICRA, Robotics: Science and Systems, Humanoids, Hybrid Systems: Computation and Control, as well as the inaugural best paper award from the IEEE RAS Technical Committee on Whole-Body Control.

##
25.01.23, Amanda Prorok, Cambridge University: Learning Cooperative Control Policies for Multi-Robot Systems

**Wednesday, January 25th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**In this talk, I discuss how we leverage machine learning methods to generate cooperative policies for multi-agent / multi-robot systems. I describe how we use Graph Neural Networks (GNNs) to learn effective communication strategies for decentralized coordination across various multi-agent tasks. In particular, I will discuss recent work on the role of agent heterogeneity and its impact on transferring learned cooperative policies to real-world experimental settings.

##
01.02.23, Maarten Löffler, Utrecht University and Tulane University: Labeled & Unlabeled Reconfiguration by Compaction

**Wednesday, February 1st, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**

We consider configurations of (labeled or unlabeled) objects on an integer lattice, and their behaviour under compaction operations: we may think of these as globally pushing all objects with a horizontal or vertical half-plane by one unit, where objects will also push other objects which are in the way. Under this model, the central question is: given two configurations of the same set of objects, is there a sequence of compaction operations that will transform the first configuration into the second. In this talk, we will consider both the characterization of such configuration pairs where the answer is yes, and the computational complexity of answering this question in general as well as in some special cases.

##
08.02.23, Michael Bilevich, Tel Aviv University: Sensor Localization by Few Distance Measurements via the Intersection of Implicit Manifolds

**Wednesday, January 4th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**

Robot localization is the task of determining a robot’s position and orientation (pose) inside an environment using data collected from sensors. As such, localization is a key ingredient in robot navigation and other tasks, which has received a lot of attention over the years.

In this talk we will present a general approach for determining the unknown (or uncertain) pose of a sensor mounted on a robot in a known environment, using only a few distance measurements (between 2 to 6 typically), which is advantageous, among others, in sensor cost, and storage and information-communication resources.

We will discuss the underlying geometry of the problem at hand, and how it can be utilized to derive a simple-to-implement and easy-to-parallelize algorithm for numerical estimation of the sensor pose using a few distance measurements.

We will demonstrate the real-time effectiveness of our method even at high accuracy on a variety of scenarios and different allowable intermediate motions between measurements. We will also present experiments with a physical robot.

This is a joint work with Steven M. LaValle and Dan Halperin.

To appear in ICRA 2023.

##
20.10.21, Steven M. LaValle, University of Oulu: Goldilocks and the Robot Brains

**Wednesday, October 20th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**Imagine building a robot to accomplish one or more tasks, such as

vacuuming, patrolling, or exploration. This talk considers an

egocentric or situated view of theoretical robot development that

takes into account its space of possible environments and specific

tasks. How much does a robot need to sense and remember to

successfully interact with its environment? This question is

fundamental to robotics and distinguishes it from other fields such as

computer science or control theory. If machine learning is the goal,

then the question becomes what are the minimal, ideal structures

that could possibly be learned? Thus, emphasis in this talk is placed

on determining the minimal amount of information necessary to solve

tasks, thereby giving the robot the smallest possible “brain”. At one

extreme, strong geometric information is sensed and encoded, leading

to problems such as classical motion planning. On the path to

minimalism, weak geometric information is considered in the form of

combinatorial or relational sensing and filtering. Eventually,

topological and set-based representations are considered at the

minimalist extreme.

##
27.10.21, Erin Wolf Chambers, Saint Louis University: Applications of Topology and Geometry to Root Analysis

**Wednesday, October 27th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**Analysis of 3d shapes is a core problem in many fields, and there are many

tools from topology and geometry that can provide insight and understanding. In

this talk, we focus on developing significance measures for 3d plant

structures, primarily root systems of plants. Our measures are based on the

medial axis transform, which plays a fundamental role in shape matching and

analysis, but is widely known to be unstable to even small boundary

perturbations. Methods for pruning the medial axis are usually guided by some

measure of significance, with considerable work done for both 2- and

3-dimensional shapes. Such significance measures can be used for identifying

salient features, and hence are useful for simplification, comparison, and

alignment. In this talk, we will present theoretical insights and properties of

commonly used significance measures, focusing on those in 2D and 3D that are

both shape-revealing and topology-preserving, as well as being robust to noise

on the boundary. We’ll then discuss several methods that de-noise a shape and

identify topologically and geometrically prominent features, using both the

medial axis and other measures commonly used in topological data analysis. Our

methods are quite successful compared to the state of the art, and are

available in the package TopoRoot, an automatic pipeline for plant

architectural analysis from 3D Imaging

##
03.11.21, **No seminar**

**No seminar**

##
10.11.21, Rachel Holladay, MIT: Constraints and Planning for Forceful Robotic Manipulation

**Wednesday, November 10th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**Enabling robots to perform multi-stage forceful manipulation tasks, such as

##
17.11.21, Timothy Chan, UIUC: Hopcroft's Problem Revisited (or How to Shave a Log-Star)

**Wednesday, November 17th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**In this talk, I will describe new algorithms to find incidences between n

points and n lines in 2D in O(n^{4/3}) time, improving Matousek’s previous result

from 30 years ago by a 2^{O(log^*n)} factor. The new techniques have applications

to numerous other range-searching-related problems (in 2D and higher), allowing

us to remove extraneous factors from many known theoretical time bounds.

Joint work with Da Wei Zheng (to appear in SODA’22).

##
24.11.21, Oren Salzman, Technion: Multi-Agent Path Finding: New Analysis, Problem Variants and Algorithms

Wednesday, November 24th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)

**Abstract:**The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of

conflict-free paths for a fleet of agents operating in a given environment. It

has applications in diverse domains such as warehouse automation, pipe routing

and more. This problem has been extensively studied by the planning community

in the last decade. Indeed, the tools developed to address this problem were

used to dramatically outperform learning-based approaches in the recent 2020

Flatland Challenge—a NeurIPS competition trying to determine how to

efficiently manage dense traffic on rail networks.

Arguably, the state-of-the-art approach to computing optimal solutions to the

MAPF problem is Conflict-Based Search (CBS). In this talk I will describe

recent work where we revisit the complexity analysis of CBS to provide tighter

bounds on the algorithm’s run-time in the worst-case. Our analysis paves the

way to better pinpoint the parameters that govern (in the worst case) the

algorithm’s computational complexity. Following this theoretical analysis, I

will shift to describe two new variants of the MAPF problem, both motivated by

real world applications, and describe algorithmic approaches to solve these

variants.

The talk is based on work done by Ofir Gordon, Nir Greshler, David Weinstein

and Nitzan Madar with the support of Yuval Filmus and Nahum Shimkin and myself.

##
01.12.21, Mikkel Abrahamsen, University of Copenhagen: Online Sorting and Translational Packing of Convex Polygons

**Wednesday, December 1st, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**

Packing problems regularly appear in everyday life and also in industrial

settings such as shipping, production of clothing, sheet metal cutting, etc. In

this talk, we investigate various online packing problems in which convex

polygons arrive one by one and have to be placed irrevocably into a container

before the next piece is revealed; the pieces must not be rotated, but only

translated. The aim is to minimize the used space depending on the specific

problem at hand, e.g., the strip length in strip packing, the number of bins in

bin packing, etc.

We draw interesting connections to the following online sorting problem: We

receive a stream of real numbers $s_1, \ldots, s_n$, $s_i \in [0,1]$, one by one.

Each real must be placed in an array $A$ with $Cn$ initially empty cells

without knowing the subsequent reals, for a constant $C\geq 1$. The goal is to

minimize the sum of differences of consecutive reals in $A$. It follows that

the offline optimum is to place the reals in sorted order so the cost is at

most $1$. We show that there is no competitive algorithm for this problem.

We use this lower bound to answer several fundamental questions about packing.

Specifically, we prove the non-existence of competitive algorithms for various

online translational packing problems of convex polygons, among them strip

packing, bin packing and perimeter packing.

Joint work with: Anders Aamand, Lorenzo Beretta, Linda Kleist.

##
08.12.21, Dror Dayan, Tel Aviv University: Near-Optimal Multi-Robot Motion Planning with Finite Sampling

**Wednesday, December 8th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**

An underlying structure in several sampling-based methods for continuous

multi-robot motion planning (MRMP) is the tensor roadmap, which emerges

from combining multiple probabilistic roadmap (PRM) graphs constructed for the

individual robots via a tensor product. We study the conditions under which the

tensor roadmap encodes a near-optimal solution for MRMP—satisfying these

conditions implies near optimality for a variety of popular planners, including

dRRT*, and the discrete methods M* and conflict-based search, when applied to

the continuous domain.

We develop the first finite-sample analysis of this kind, which specifies the

number of samples, their deterministic distribution, and magnitude of the

connection radii that should be used by each individual PRM graph, to guarantee

near-optimality using the tensor roadmap.

This significantly improves upon a previous asymptotic analysis, wherein the

number of samples tends to infinity. Our new finite sample-size analysis

supports guaranteed high-quality solutions in practice within finite time.

To achieve our new result, we first develop a sampling scheme, which we call

the staggered grid, for finite-sample motion planning for individual

robots, which requires significantly less samples than previous work. We then

extend it to the much more involved MRMP setting which requires to account for

interactions among multiple robots. Finally, we report on a few experiments

that serve as a verification of our theoretical findings and raise interesting

questions for further investigation.

This is joint work with Kiril Solovey, Marco Pavone, and Dan Halperin.

##
15.12.21, Natan Rubin, Ben Gurion University: Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions

**Wednesday, December 15th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**

Given a finite point set $P$ in $R^d$, and $\eps>0$ we say that a point set $N$

in $R^d$ is a weak $\eps$-net if it pierces every convex set $K$ with

$|K \cap P| \geq \eps |P|$.

Let $d\geq 3$. We show that for any finite point set in $R^d$, and any

$\eps>0$, there exists a weak $\eps$-net of cardinality $o(1/\eps^{d-1/2})$,

where \delta>0 is an arbitrary small constant.

This is the first improvement of the bound of $O^*(1/\eps^d)$ that was obtained

in 1993 by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl for

general point sets in dimension $d \geq 3$.

##
22.12.21, Tzvika Geft, Tel Aviv University: Refined Hardness of Multi-Robot/Agent Motion Planning

Wednesday, December 22nd, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)

**Abstract:**

In Multi-Robot Motion Planning (MRMP) we aim to plan collision-free motion of

robots from given start to target positions in a common workspace. While the

general problem has been known to be intractable for decades, the reasons

behind its difficulty are still not well-understood. I will present new

complexity results for MRMP and its discrete counterpart, called Multi-Agent

Pathfinding (MAPF), where the robots are modeled as agents on a graph.

First, we study distance-optimal MAPF, i.e., where the objective is minimizing

the total distance travelled. The tightest hardness result for distance-optimal

MAPF so far were for planar graphs. However, MAPF formulations commonly further

restrict the input graph to be a 2D grid, as grids naturally model well-structured

environments such as warehouses. Following this gap, Banfi et al. (2017) posed

the tractability on 2D grids as an open question, which we settle by showing

that this case remains NP-hard. We improve on previous hardness results in the

additional following ways: Our reduction is directly from 3-SAT using simple

gadgets, making it arguably more helpful for identifying the source of

hardness. Secondly, the reduction is the first linear one for the planar case.

This results in the first exponential lower bound for the problem’s running

time, based on the Exponential Time Hypothesis.

Next, we turn to monotone MRMP, a natural NP-hard restriction of MRMP where

robots move one by one to their targets. We examine two tractable variants of

the problem that become NP-hard when their formulation is altered slightly.

These sharp changes in the problem’s computational complexity shed new light on

its tractability frontier.

Joint work with Dan Halperin.

##
29.12.21, **No seminar**

**No seminar**

##
05.01.22, Esther Ezra, Bar Ilan University: Arc-Intersection Queries Amid Triangles in Three Dimensions and Related Problems

### Wednesday, January 5th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)

**Abstract:**

##
09.03.22, Michael Bilevich, Tel Aviv University: Motion Planning Transformers

### Wednesday, March 9th, 5:10pm Tel Aviv time (4:10pm CET, 10:10am NY time)

**Abstract:**

##
16.03.22, **No seminar**

**No seminar**

##
30.03.22, Barak Ugav, Tel Aviv University: Localization with Few Distance Measurements

**Wednesday, March 30th, 5:10pm Tel Aviv time (4:10pm CET, 10:10am NY time)**

**Abstract:**

The robot localization problem has been researched for many years with many

variants, but what if the robot is limited in the number of distance

measurements it is able to perform?

In this talk I will present a variant with only a few (one or two) distance

measurements, and an algorithm to address this case, which preprocesses the

scene to support queries given a few distance measurement values.

This is joint work with Dan Halperin and Steven M. LaValle.

##
06.04.22, Tzvika Geft, Tel Aviv University: Recent Progress in Multi-Robot/Agent Motion Planning

**Wednesday, April 6th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**

In Multi-Robot Motion Planning (MRMP) we aim to plan collision-free motion of

robots from given start to target positions. Multi-Agent Path Finding (MAPF) is

a discretized version of MRMP, where the robots are agents moving on a graph.

In this talk, I will describe recent results and work in progress for a few

MAPF variants. For the flow time objective, where the goal is to minimize the

sum of arrival times of all agents, I will present a restricted case in which

the problem becomes tractable. I will then shift to describing a heuristic

algorithm for the total distance objective, where the aim is to minimize the

total distance travelled. The algorithm’s main innovation is a global

outlook-based method of dynamic prioritization and adaptive paths. Experiments

show that the algorithm quickly finds solutions better than 1.05-optimal for

grids that have up to 25% of their vertices occupied by agents. This part of

the talk is based on joint work with Noam Geller, Michael Bilevich, and Dan

Halperin. If time permits, I will discuss progress on additional MAPF/MRMP

variants.

##
02.05.22, Mikkel Abrahamsen, University of Copenhagen: Tiling with Squares and Packing Dominos in Polynomial Time

**Wednesday, November 2nd, 4:10pm Tel Aviv time (3:10pm CET)**

**Abstract:**

We resurrect, extend and generalize a technique, developed 7 years ago for a Frechet distance problem,

and show that it can solve a large collection of geometric optimization problems, significantly improving known solutions,

for example for the reverse shortest path problem on unit-disk graphs, and obtaining new and fast solutions to other problems.

The technique is a simpler alternative to (or variant of) parametric search, for problems where the decision procedure is hard to

parallelize. The new algorithms make effective use of, and develop further, semi-algebraic range searching, a central topic in

geometry, where efficient implementations of the technique have emerged only very recently.

Joint work with Pankaj Agarwal and Matya Katz

##
01.06.22, Chaya Keller, Ariel University: A Solution to Ringel’s Circle Problem

**Wednesday, June 1st, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)**

**Abstract:**In 1959, Gerhard Ringel posed the following problem: What is the maximal number of colors needed for coloring any collection of circles, no three tangent at a point, such that any two tangent circles get different colors?

The special case where the circles are non-overlapping was shown long ago to be equivalent to the celebrated 4-color theorem. The general case has remained open; it was only known that 4 colors are not sufficient. In this talk we show that no finite number of colors can suffice, by constructing collections of circles whose tangency graphs have an arbitrarily large girth (so in particular, no three are tangent at a point) and an arbitrarily large chromatic number. Our construction, which is one of the first geometric constructions of graphs with a large girth and a large chromatic number, relies on a (multidimensional) version of Gallai’s theorem with polynomial constraints, which may be of independent interest.

Joint work with James Davies, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak

##
15.06.22, Yahav Avigal, UC Berkeley: The Need For Speed: Enabling Real-Time Manipulation Through Optimization, Simulation and Deep Learning

**Wednesday, June 15th, 4:10pmCheckPoint 480**

**Abstract:**Robots have the potential to increase productivity and reduce costs and injuries in a variety of industries, including logistics, manufacturing, agriculture, surgical procedures and healthcare. To do so, robots are required to operate robustly, reliably and increasingly more efficiently in unstructured or semi-structured environments under a high degree of uncertainty in perception and control. In this presentation, I will describe my work on improving and enabling efficient robot manipulation by addressing challenges in sensing, planning and control through optimization, simulation and deep learning.

##
04.11.20, Sariel Har-Peled, UIUC: Reliable spanners

**Wednesday, November 4th, 16:10**

**Abstract:**A spanner is reliable if it can withstand large catastrophic

failures in the network. More precisely, any failure of some nodes can

only cause a small damage in the remaining graph in terms of the

dilation. That is, the spanner property is maintained for almost all

the nodes in the residual graph. We will discuss recent results on

this problem, including (a) constructions of reliable spanners of near

linear size in the low-dimensional Euclidean settings, and (b)

constructions of reliable spanners for planar graphs, trees and

(general) metric spaces.

Based on joint work with Kevin Buchin and Dániel Olah, in the

following papers:

https://arxiv.org/abs/2007.08738

https://arxiv.org/abs/1912.01547

https://arxiv.org/abs/1811.06898

##
11.11.20, Wolfgang Mulzer, FU Berlin: Long alternating paths exist

**Wednesday, November 11th, 16:10**

**Abstract:**Let P be a set of 2n points in convex position, such that n

points are colored red and n points are colored blue. A non-crossing

alternating path on P of length l is a sequence p_1, …, p_l of l

points from P so that (i) all points are pairwise distinct; (ii) any two

consecutive points p_i, p_{i+1} have different colors; and (iii) any two

segments p_i p_{i+1} and p_j p_{j+1} have disjoint relative interiors,

for i /= j.

We show that there is an absolute constant eps > 0, independent of n and

of the coloring, such that P always admits a non-crossing alternating

path of length at least (1 + eps)n. The result is obtained through a

slightly stronger statement: there always exists a non-crossing

bichromatic separated matching on at least (1 + eps)n points of P. This

is a properly colored matching whose segments are pairwise disjoint and

intersected by a common line. For both versions, this is the first

improvement of the easily obtained lower bound of n by an additive term

linear in n. The best known published upper bounds are asymptotically of

order 4n/3 + o(n).

Based on joint work with Pavel Valtr.

##
18.11.20, Irina Kostitsyna, TU Eindhoven: Multi-robot motion planning for disc robots

**Wednesday, November 18th, 16:10**

**Abstract:**

Given a set of robots in a geometric environment, the multi-robot motion planning problem is to find a schedule and paths for the robots to move from their initial positions to a set of target locations while avoiding collisions. We can distinguish between labeled and unlabeled versions of the problem. In the labeled version, the robots are prescribed to which specific target locations to move, and, in the unlabeled version, the robots are indistinguishable and can move to any target location. Finally, the k-color multi-robot motion planning generalizes the two versions: Given k classes of robots, it prescribes a robot class to each target location but not a specific robot within this class. In this talk I will present some recent results on the unlabeled and k-color multi-robot motion planning for disc robots.

Based on joint work with Thomas Brocken, Wessel van der Heijden, Lloyd Lo-Wong, Remco Surtel, Stijn Slot, Bahareh Banyassady, Mark de Berg, Kevin Buchin, Karl Bringmann, Henning Fernau, Dan Halperin and Yoshio Okamoto

##
25.11.20, Florian Pokorny, KTH Royal Institute of Technology: Some methods for reasoning about topology & global geometry in machine learning & robotics

**Wednesday, November 25th, 16:10**

**Abstract:**In this talk, I will discuss some applications of ideas from topological

data analysis based on the use of Delaunay-Cech and Alpha complexes.

Use cases in robotics include motion clustering as well as applications

to motion planning, caging/path non-existence and the analysis of

configuration spaces, while applications to machine learning include the

classification and topological data analysis of image data. In

particular, I will discuss some or our recent work on developing

randomized approximation algorithms that allow one to apply these ideas

in higher dimensions [ICML’19 & KDD’20, Polianskii & Pokorny] and we

will then discuss some of the challenges that remain in this area.

##
02.12.20, Elon Rimon, Technion: Configuration space perspectives on minimalistic robot hands and a caging-based biohazard sample handling robot

**Wednesday, December 2nd, 16:10**

**Abstract:**

Ten years of research on minimalistic robot hands resulted in novel robot hand

designs and culminated in a new book, The Mechanics of Robotic Grasping by

Rimon and Burdick. Perspectives gained from this activity will be shared in a talk

that will consist of two related parts. Part I describes the configuration space analysis

of multi-finger grasps. In so doing, we obtain the minimalistic 2-D and 3-D robot

hand designs in terms of number of fingers.

Surprise: the minimalistic 3-D design is the classical 3-finger Salisbary Hand, with

added security of using the hand’s palm when object immobilization is necessary.

Part II considers the notion of caging, which offers a robust object grasping

methodology under huge uncertainty in the finger positions. A novel contact

space approach resulted in a series of highly efficient and intuitive

caging-to-grasping algorithms, specifically suited for minimalistic robot

hands. Two such algorithms will be described for 3-finger robot hands grasping

2-D objects. Using caging grasp for 3-D objects, a new table-top robot that

opens biohazard sample-kits in biomedical will be described.

**Short bio: **

Elon Rimon is a Professor in the Department of Mechanical Engineering at the

Technion. Professor Rimon was a finalist for the best paper awards at the IEEE

International Conference on Robotics and Automation and the Workshop on Algorithmic

Foundations of Robotics, and he was awarded best paper presentation at the

Robotics Science and Systems Conference. Professor Rimon is the lead author of the

new Mechanics of Robot Grasping text, published by Cambridge University Press.

##
09.12.20, Omrit Filtser, SUNY Stony Brook: Static and streaming data structures for Fréchet distance queries

**Wednesday, December 9th, 16:10**

**Abstract:**

Measuring the similarity of two curves or trajectories is an important task that arises in various applications. The Fréchet distance and its variants became very popular in the last few decades, and some were successfully applied to real data sets. The Fréchet distance between two curves can be computed in quadratic time using a simple dynamic programming algorithm. However, under SETH, no strongly subquadratic algorithms exist, even if the solution may be approximated up to a factor of 3. Therefore, in applications where the curves in the given data set are large, a natural solution is to construct a data structure that allows fast distance queries.

In this talk I will discuss approximate distance oracles and nearest neighbour search data structures under the discrete Fréchet distance. In addition, I will present an algorithm that constructs simplifications in the streaming model, an oracle for distance queries to a sub-curve, and introduce the zoom-in problem.

Based on joint works with Arnold Filtser and Matya Katz.

##
16.12.20, Sándor Fekete, TU Braunschweig: Geometric algorithms for large robot swarms

**Wednesday, December 16th, 16:10**

**Abstract:**

Modern robotics has achieved many impressive feats for the navigation of individual robots, making

autonomous vehicles a reality. However, just like in road traffic, many of the really complex challenges

arise from the interaction and coordination of many robots; this requires an array of methods,

in particular, making use of geometry.

I will present an overview of challenges arising from coordination and reconfiguration of swarms of many

objects, ranging in size from minuscule particles all the way to far-away satellite swarms.

Algorithmic results include (1) the exploration of unknown environments by large groups of robots,

(2) controlling the motion of many tiny particles by an external force, (3) coordinating the collision-free motion

of many robots, vehicles, aircraft, or people, such that each one reaches its destination as quickly as possible

(the subject of the Computational Geometry Challenge 2021), and (4) how to use simple robots to construct

large-scale structures, such as space stations.

##
23.12.20, Tzvika Geft, TAU: Algorithms for two-handed planar assembly partitioning with connectivity constraints

**Wednesday, December 23rd, 16:10**

**Abstract:**

Assembly planning, which is a fundamental problem in robotics and automation, aims to design a sequence of motions that will bring the separate constituent parts of a product into their final placement in the product. It is convenient to study assembly planning in reverse order, where the following key problem, assembly partitioning, arises: Given a set of parts in their final placement in a product, partition them into two sets, each regarded as a rigid body, which we call a subassembly, such that these two subassemblies can be moved sufficiently far away from each other, without colliding with one another. The basic assembly planning problem is further complicated by practical consideration such as how to hold the parts in a subassembly together. Therefore, a desired property of a valid assembly partition is for each of the two subassemblies to be connected.

We previously showed that even the following simple case of the connected-assembly-partitioning problem is NP-complete: Given a connected set A of unit grid squares in the plane, find a connected subset S of A such that A\S is also connected and S can be rigidly translated to infinity along a prescribed direction without colliding with A\S.

In this talk the previous hardness result will be complemented with two positive results for the aforementioned problem variant for grid square assemblies.

First, we show that it is fixed parameter tractable and give an O(2^k n^2)-time algorithm, where n=|A| and k=|S|. Second, we describe a special case of this variant where a connected partition can always be found in linear time. Each of the positive results sheds further light on the special geometric structure of the problem at hand.

To appear in SODA 2021.

Joint work with Pankaj K. Agarwal, Boris Aronov, and Dan Halperin

##
30.12.20, Esther Ezra, Bar Ilan University: On ray shooting amid triangles in three dimensions and related problems

**Wednesday, December 30th, 16:10**

**Abstract:**

We consider several problems that involve lines in three dimensions, and present improved algorithms for solving them. The problems include (i) ray shooting amid triangles in three dimensions, (ii) reporting intersections between query lines (segments, or rays) and input triangles, (iii) computing the intersection of two nonconvex polyhedra, (iv) detecting, counting, or reporting intersections in a set of lines in 3-space, and (v) output-sensitive construction of an arrangement of triangles in three dimensions. Our approach is based on the polynomial partitioning technique. For example, our ray-shooting algorithm processes a set of n triangles in R^3 into a data structure for answering ray shooting queries amid the given triangles, which uses O(n^{3/2+\eps}) storage and preprocessing, and answers a query in O(n^{1/2+\eps}) time, for any \eps > 0. This is a significant improvement over known results, obtained more than 25 years ago, in which, with this amount of storage, the query time bound is roughly n^{5/8} . The algorithms for the other problems have similar performance bounds, with similar improvements over previous results.

Joint work with Micha Sharir.

##
06.01.21, Alex Steiger, Duke University: Decomposing the complement of the union of cubes

**Wednesday, January 6th, 16:10**

**Abstract:**

We consider the problem of decomposing a 3D region into simple regions, which is an important problem in motion planning and solid modeling. Specifically, we consider the case where the 3D region is implicitly defined as the common exterior of a set of N axis-aligned cubes, and we wish to partition the common exterior into boxes with pairwise-disjoint interiors. Since the cubes may intersect, the combinatorial complexity K of the boundary of the union may be as small as O(1) and as large as O(N^2). Furthermore, K is a lower bound for the size of the smallest decomposition.

We present an algorithm to compute a decomposition of size O(K polylog N) in comparable time. For the case where all cubes are congruent, we present a simpler algorithm to compute a decomposition of size O(N log N). These results improve upon decompositions of size O(K^{3/2}) from previous work.

This talk is based on joint work with Pankaj K. Agarwal and Micha Sharir.

##
06.11.19, Sivan Toledo, TAU: Using Delaunay Triangulations to Cluster Eigenvalues of Matrices

**Wednesday, November 6th, 2019, 16:10**

**Abstract:**A function f(A) of a square real or complex matrix A is a matrix with the same eigenvectors but with eigenvalues that have been transformed by some scalar function, such as f(x)=sin(x) or f(x)=sign(x). For a few simple functions, there are O(n^3) algorithms to compute f(A). For most, there is not. One algorithm that can often achieve performance close to O(n^3) and is very general is a block recurrence in which A is first transformed to its Schur form A=U*T*U’, where U is unitary and T upper triangular. Then the eigenvalues of A, which are the diagonal elements of T, are clustered and the Schur form is reordered so that clusters are contiguous. Then some other algorithm to evaluate f(A) is applied to diagonal blocks of T that correspond to clusters, such as a Pade approximation. Then the algorithm solves for the offdiagonals of f(A) by solving Sylvester equations. If the clusters are far apart enough, the Sylverster solver tends to be numerically stable (we would love to guarantee it, but it’s too hard). It turns out that the clustering problem is equivalent to the partitioning of a graph, whose vertices are the eigenvalues, into connected components. Our main result shows that we can replace the graph that arises in this problem by the Delaunay triangulation of the eigenvalues, thereby reducing the complexity from quadratic to O(n log n).

This is joint work with Nir Goren and Dan Halperin.

##
13.11.19, Yair Marom, University of Haifa: k-Means Clustering of Lines for Big Datas

**Wednesday, November 13th, 2019, 16:10**

**Abstract:**The input to the k-mean for lines problem is a set L of n lines in R^d, and the goal is to compute a set of k centers (points) in R^d that minimizes the sum of squared distances over every line in L and its nearest center. This is a straightforward generalization of the k-mean problem where the input is a set of n points instead of lines

We suggest and the first PTAS that computes a (1+epsilon)-approximation to this problem in time O(n log n) for any constant epsilon>0, and k, d > 1.

Streaming input using ~log(n) memory, and distributed parallel computations are also provided.

This is by proving that there is always a weighted subset (called coreset) of dk^{O(k)} log (n)/epsilon^2 lines in L that approximates the sum of squared distances from L to any given set of k points.

Experimental results, open source, and applications for anomaly detection and localization via standard (2D) cameras are also provided.

Based on a NIPS’19 paper, co-authored with Dan Feldman

##
20.11.19, Avishai Sintov, TAU: Motion Planning Around Obstacles with Convex Optimization

**Wednesday, November 20th, 2019, 16:10**

**Abstract:**

ndustrial manipulation of rigid objects has been automated for quite a long time, while the handling of deformable objects is usually done manually due to the lack of feasible motion planning algorithms. Motion planning algorithms have mainly focused on the manipulation of rigid bodies by one or more robots. Consequently, much less attention has been given to motion planning for the manipulation of deformable objects in general, and elastic rods in particular.

In the talk I will use an analytical description of the configuration space of elastic rods to present a motion planning algorithm for robotic manipulation that is easy to implement and works well in practice. Previous work has shown that the configuration space of an elastic rod, i.e., the set of all equilibrium configurations, is a six-dimensional smooth manifold. This remarkable discovery enables the use of standard sampling-based motion planners to easily plan the manipulation of such rods with two robotic arms. However, this usually results in high computational costs due to a large amount of time spent in solving ordinary differential equations. Hence, I will present an advanced approach to plan motions over two dimensional slices in the free configuration space of the rod. These slices are based on the scale invariance property of the rod, they show that the configuration space of a rod is path-connected and they enable low-cost computations.

##
27.11.19, **No seminar**

**No seminar**

##
04.12.19, Khen Elimelech, The Technion: Efficient Decision Making and Belief Space Planning using Sparse Approximations

**Wednesday, December 4th, 2019, 16:10**

Checkpoint 480

**Abstract:**These days, intelligent autonomous agents and robots can be found all around us. These agents share the same fundamental goal — to autonomously plan and execute their actions. In order to achieve reliable and robust performance, these agents should account for real-world uncertainty. Also, problems, such as long-term autonomous navigation, active Simultaneous Localization and Mapping (SLAM), and sensor placement over large areas, often involve optimization of numerous variables. These settings require reasoning over high-dimensional probabilistic states, known as “beliefs”. Appropriately, the corresponding problem is known as Belief Space Planning (BSP). The computational complexity of this problem can turn exceptionally high, thus making it challenging for online systems, or when having a limited processing power.

In the first part of this talk, we will formulate the BSP problem, and state-of-the-art solution methods. In the second part, we will introduce fundamental work towards efficient decision making via problem simplification. We will show that a wise simplification method can maintain the same action selection (“action consistency”), or one for which the maximal loss can be guaranteed. We will then practically apply these ideas to BSP problems, in which the problem can be simplified by considering a sparse approximation of the initial belief. Finally, we will demonstrate the benefits of the approach in the solution of a highly realistic active-SLAM problem, where we manage to significantly reduce computation time, with practically no loss in the quality of solution.

##
11.12.19, Gabriel Nivasch , Ariel: How to Peel Self-Intersecting Onions

**Wednesday, December 11th, 2019, 16:10**

Checkpoint 480

**Abstract:**

We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between “grid peeling” and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids.

Although this experimental connection seems hard to prove, we do prove that HCS satisfies some simple properties analogous to those of ACSF.

Joint work with Sergey Avvakumov (IST Austria).

Links:

https://arxiv.org/abs/1909.00263

https://youtu.be/HaGVe5LnsEg

https://youtu.be/D3mFSAfzuJM

##
18.12.19, **No seminar**, The planned talk is postponed due to unexpected circumstances

**No seminar**, The planned talk is postponed due to unexpected circumstances

##
25.12.19, Shay Solomon, Tel Aviv University: Truly Optimal Euclidean Spanners

**Wednesday, December 25th, 2019, 16:10**

**Abstract:**

A Euclidean (1 + ϵ)-spanner for a point set S in the d dimensional Euclidean space R^d is a subgraph of the complete Euclidean graph corresponding to S, which preserves all pairwise distances to within a factor of 1 + ϵ.

Geometric spanners find many applications, from compact routing and distance oracles to robotics and machine learning. In many of those applications, the spanners should be sparse either in the unweighted sense (small number of edges) or in the weighted sense (small weight).

Cornerstone results in the area from the 80s and 90s state that for any n-point set in R^d, there exists a (1+ϵ)-spanner with n O(ϵ^{−d+1}) edges and lightness (normalized weight) O(ϵ^{−2d}).

Surprisingly, the question of whether or not these dependencies on ϵ and d for small d can be improved has remained elusive, even for d=2.

In this talk I’ll discuss this question and a few related questions, focusing mostly on the case d = 2.

The talk is self-contained and no prior knowledge is assumed.

Part of the talk is based on a joint work with Hung Le, https://arxiv.org/abs/1904.12042

##
01.01.20, Micha Sharir, TAU: On the Existence and Synthesis of Multifinger Positive Grips

**Wednesday, January 1st, 2020, 16:10**

**Checkpoint 480**

**Abstract:**The talk will review an old paper with the same title, by B, Mishra, J.T. Schwartz and M. Sharir (Algorithmica 1987). The paper gives bounds on the number of friction-free fingers that are needed to grasp any object (satisfying some natural properties) in two or three dimensions. To grasp the object, each finger can exert some force in the direction of the inner normal at the point of contact. One either wishes to keep the body at equilibrium, or to resist (balance) a given external force and torque, or to be able to balance any force and torque, with a suitable set of forces that the fingers exert, without moving the contact points. The paper also presents efficient algorithms for constructing suitable contact points for a polyhedral object.

##
08.01.20, **No seminar**

**No seminar**

**Wednesday, July 7th, 2020, 16:10**

**Golan Miglioli-Levy, TAU**

**Abstract:**In this tutorial I will share some of my experience with the GeoGebra tool — a free (online) interactive tool for mathematical

operations — focusing on the visualization and geometric

capabilities of GeoGebra. The tutorial will consist of the

following sections:

- Why should you use GeoGebra
- The basics
- Create, load, save and share projects
- Produce and export figures for papers (+ tips)
- Explore geometric properties
- Object dependency and custom tools
- Step-by-step examples

### Recording:

Zoom

### Presentation:

PowerPoint

##
15.01.20, Matya Katz, BGU: Approximate Nearest Neighbor for Curves – Simple, Efficient, and Deterministic

**Wednesday, January 15th, 2020, 16:10**

**Checkpoint 480**

**Abstract:**In the (1+\eps,r)-approximate near-neighbor problem for curves (ANNC) under some distance measure \delta, the goal is to construct a data structure for a given set \C of curves that supports approximate near-neighbor queries: Given a query curve Q, if there exists a curve C \in \C such that \delta(Q,C) \le r, then return a curve C’ \in \C with \delta(Q,C’) \le (1+\eps)r.

There exists an efficient reduction from the (1+\eps)-approximate nearest-neighbor problem to ANNC, where in the former problem the answer to a query is a curve C \in \C with \delta(Q,C) \le (1+\eps)\delta(Q,C^*), where C^* is the curve of \C closest to Q.

Given a set \C of n curves, each consisting of m points in d dimensions, we construct a data structure for ANNC that uses n \cdot O(1/\eps)^{md} storage space and has O(md) query time (for a query curve of length m), where the similarity between two curves is their discrete Fr \’echet or dynamic time warping distance. Our method is simple to implement, deterministic, and results in an exponential improvement in both query time and storage space compared with all previous work.

We also consider the asymmetric version of ANNC, where the length of the query curves is k << m, and obtain essentially the same storage and query bounds as above, except that m is replaced by k.

Based on joint work with Arnold Filtser and Omrit Filtser.

##
22.01.20, Tamar Flash, Weizmann: From Observed Motor Behavior to Computational Models: Human Motion Planning, Compositionality and Timing

**Wednesday, January 22nd, 2020, 16:10**

**Checkpoint 480**

**Abstract:**Behavioral and computational studies have focused on identifying the spatial and temporal characteristics of various movements ranging from simple reaching to

to complex 2D and 3D motions. Such features were quite instrumental in investigating the organizing principles that underlie trajectory formation by the brain. Similar kinematic principles also play a critical role in visual perception of motion and in action recognition. In my talk I will present a new theory of trajectory formation, which is inspired by invariance theory. The theory proposes that movement time, kinematics, and compositionality arise from the mixture of Euclidian and several Non-Euclidian geometries. Mathematically expressing these ideas, a computational scheme was used in modeling 2D and 3D hand and locomotion trajectories and accounting for motion singularities. I will also present motion planning models that combine geometric and optimization approaches to motion segmentation and discuss several behavioral and brain imaging studies supporting the mixture of geometries model and the similarities between motion perception and production. Finally I will discuss motor timing of human movements- what principles and models account for the selection of both global durations and durations of individual movement segments within complex actions. I will conclude by discussing the implications of the above studies for human-robot interaction and biorobotics.

##
13.05.20, Tzvika Geft, TAU: Partitioning an Assembly into Two Connected Subassemblies is NP-Complete even for Single Translation of Unit Squares

**Wednesday, May 13th, 2020, 16:10**

**Abstract:**Assembly planning aims to design a sequence of motions that will bring the separate constituent parts of a product into their final placement in the product. It is convenient to study assembly planning in reverse order, where the following key problem, assembly partitioning, arises: Given a set of parts in their final placement in a product, partition them into two sets, each regarded as a rigid body, which we call a subassembly, such that these two subassemblies can be moved sufficiently far away from each other, without colliding with one another (sliding of one subassembly over the other, namely motion in contact, is allowed). The basic assembly planning problem is further complicated by practical consideration such as how to hold the parts in a subassembly together. Therefore, a desired property of a valid assembly partition is that each of the two subassemblies will be connected.

** **

##
20.05.20, Xavier Goaoc, Éstcole des Mines de Nancy and LORIA: Convex Hulls of Random Order Types

**Wednesday, May 5th, 2020, 16:10**

**Abstract:**

##
27.05.20, Golan Miglioli-Levy, TAU: Space-Aware Reconfiguration

**Wednesday, May 27th, 2020, 16:10**

**Abstract:**We consider the widely studied problem of reconfiguring a set of physical objects into a desired target configuration, a typical (sub)task in robotics and automation, arising in product assembly, packaging, stocking store shelves, and more.

In this paper we address a variant, which we call space-aware reconfiguration, where the goal is to minimize the physical space needed for the reconfiguration, while obeying constraints on the allowable collision-free motions of the objects.

Since for given start and target configurations, reconfiguration may be impossible, we translate the entire target configuration rigidly into a location that admits a valid sequence of moves, so that the physical space required by the start and the translated target configurations is minimized.

We investigate two variants of space-aware reconfiguration for the often examined setting of $n$ unit discs in the plane, depending on whether the discs are distinguishable (labeled) or indistinguishable (unlabeled). For the labeled case, we propose a representation of size $O(n^4)$ of the space of all feasible translations, and use it to find, in $O(n^6)$ time, a shortest valid translation, or one that minimizes the enclosing circle or axis-aligned box of both the start and target configurations.

For the significantly harder unlabeled case, we show that for almost every direction, there exists a translation that makes the problem feasible.

We use this to devise heuristic solutions, where we optimize the translation under stricter notions of feasibility.

We present an implementation of such a heuristic, which solves unlabeled instances with hundreds of discs in seconds.

Joint work with Dan Halperin, Marc v.Kreveld and Micha Sharir.

**Recordings:**

Zoom meeting

##
03.06.20, Esther Ezra, Bar Ilan University: Testing Polynomials for vanishing on Cartesian products

**Wednesday, June 3rd, 2020, 16:10**

**Abstract:**The 3SUM problem is to decide, given three sets A, B, C, of real numbers, whether there is a triple a \in A, b \in B, c \in C, which sums to zero.

##
10.06.20, Gabriel Nivasch, Ariel: Fusible numbers and Peano Arithmetic

**Wednesday, June 10th, 2020, 16:10**

**Abstract:**inspired by a mathematical riddle involving fuses, we define a set of rational numbers which we call “fusible numbers”. We prove that the set of fusible numbers is well-ordered in R, with order type eps_0. We prove that the density of the fusible numbers along the real line grows at an incredibly fast rate, namely at least like the function F_{eps_0} of the fast-growing hierarchy. Finally, we derive some true statements that can be formulated but not proven in Peano Arithmetic, of a different flavor than previously known such statements, for example, “For every natural number n there exists a smallest fusible number larger than n.”

Recordings:

Zoom meeting

##
17.06.20, Shakhar Smorodinsky, BGU: An Extension of Epsilon-nets for Hypergraphs with Bounded VC-dimension

**Wednesday, June 17th, 2020, 16:10**

**Abstract:**In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population or a probability distribution. For a one dimensional data set, it may be thought of as the “middle” value. A far more general notion is the classical notion of $\epsilon$-net in hypergraphs.

##
24.06.20, **No seminar** (SoCG)

**No seminar**(SoCG)

**Wednesday, July 7th, 2020, 16:10**

**Golan Miglioli-Levy, TAU**

**Abstract:**In this tutorial I will share some of my experience with the GeoGebra tool — a free (online) interactive tool for mathematical

operations — focusing on the visualization and geometric

capabilities of GeoGebra. The tutorial will consist of the

following sections:

- Why should you use GeoGebra
- The basics
- Create, load, save and share projects
- Produce and export figures for papers (+ tips)
- Explore geometric properties
- Object dependency and custom tools
- Step-by-step examples

### Recording:

Zoom

### Presentation:

PowerPoint

##
01.07.20, Kiril Solovey, Stanford: Fast Near-Optimal Heterogeneous Task Allocation via Homogeneous Decomposition

**Wednesday, July 1st, 2020, 17:10 Israel time**

**Abstract:**

Multi-robot systems are uniquely well-suited to perform complex tasks such as patrolling (and tracking), information gathering, and pick-up and delivery problems, offering significantly higher performance than single-robot systems. A fundamental building block in most multi-robot systems is task allocation: assigning robots to tasks (e.g., patrolling an area or servicing a transportation request) as they appear based on the robots’ states to maximize reward. In many practical situations, the allocation must account for potentially heterogeneous capabilities (e.g., availability of appropriate sensors or actuators) to ensure the feasibility of execution, and exploit predictive information concerning the likelihood of future tasks to promote a higher reward over a long time horizon.

To this end, we present an efficient algorithm for heterogeneous task-allocation achieving an approximation factor of at least 1/2 of the optimal reward. Our approach demonstrates that the problem can be decomposed into several homogeneous subproblems that can be solved efficiently using min-cost flow. Through simulation experiments, we show that our algorithm is faster by several orders of magnitude than a MILP-based approach.

This is joint work with Saptarshi Bandyopadhyay, Federico Rossi, Michael T. Wolf, and Marco Pavone.

##
08.07.20, **No seminar**: Geogebra Tutorial by Golan Miglioli-Levy at 16:10

**No seminar**: Geogebra Tutorial by Golan Miglioli-Levy at 16:10

**Wednesday, July 7th, 2020, 16:10**

**Golan Miglioli-Levy, TAU**

**Abstract:**In this tutorial I will share some of my experience with the GeoGebra tool — a free (online) interactive tool for mathematical

operations — focusing on the visualization and geometric

capabilities of GeoGebra. The tutorial will consist of the

following sections:

- Why should you use GeoGebra
- The basics
- Create, load, save and share projects
- Produce and export figures for papers (+ tips)
- Explore geometric properties
- Object dependency and custom tools
- Step-by-step examples

### Recording:

Zoom

### Presentation:

PowerPoint

##
24.10.18, Chaya Keller, BGU: From a (p,2) theorem to a tight (p,q) theorem

**Wednesday, October 24th, 2018, 16:10**

**Abstract:**A family F of sets is said to satisfy the (p, q)-property if among any p sets of F some q have a non-empty intersection. The celebrated (p, q)-theorem of Alon and Kleitman asserts that any family of compact convex sets in R^d that satisfies the (p, q)-property for some q ≥ d + 1, can be pierced by a fixed number (independent on the size of the family) f_d(p, q) of points. The minimum such piercing number is denoted by HD_d(p, q). Already in 1957, Hadwiger and Debrunner showed that whenever q > (d−1)p/d + 1 the piercing number is HD_d(p, q) = p − q + 1; no exact values of HD_d(p, q) were found ever since.

While for an arbitrary family of compact convex sets in R^d, d ≥ 2, a (p, 2)-property does not imply a bounded piercing number, such bounds were proved for numerous specific families. The best-studied among them is axis-parallel rectangles in the plane. Wegner and (independently) Dol’nikov used a (p, 2)-theorem for axis-parallel rectangles to show that HD_rect(p, q) = p−q + 1 holds for all q > sqrt(2p). In the talk we present a general method which allows using a (p, 2)-theorem as a bootstrapping to obtain a tight (p, q)-theorem, for families with Helly number 2. We demonstrate the power of this method by showing that HD_rect(p, q) = p−q + 1 holds for all q > 7 log p.

Based on a joint work with Shakhar Smorodinsky.

##
07.11.18, Michal Kleinbort, TAU: Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation

**Wednesday, November 7th, 2018, 16:10**

**Abstract:**The Rapidly-exploring Random Tree (RRT) algorithm has been one of the most prevalent and popular motion-planning techniques for two decades now. Surprisingly, in spite of its centrality, there has been an active debate under which conditions RRT is probabilistically complete. We provide two new proofs of probabilistic completeness (PC) of RRT with a reduced set of assumptions. The first one for the purely geometric setting, where we only require that the solution path has a certain clearance from the obstacles. For the kinodynamic case with forward propagation of random controls and duration, we only consider in addition mild Lipschitz-continuity conditions. These proofs fill a gap in the study of RRT itself. They also lay sound foundations for a variety of more recent and alternative sampling-based methods, whose PC property relies on that of RRT.

Based on a joint work with Kiril Solovey, Zakary Littlefield, Kostas E. Bekris and Dan Halperin

##
21.11.18, Ioana Bercea, TAU: Improved bounds for the Traveling Salesman Problem with Neighborhoods

**Wednesday, November 21st, 2018, 16:10**

**Abstract:**Given a set of n disks of radius R in the Euclidean plane, the Traveling Salesman Problem With Neighborhoods (TSPN) on uniform disks asks for the shortest tour that visits all of the disks. The problem is a generalization of the classical Traveling Salesman Problem (TSP) on points and has been widely studied in the literature. For the case of disjoint uniform disks of radius R, Dumitrescu and Mitchell [2003] show that the optimal TSP tour on the centers of the disks is a 3.547-approximation to the TSPN version. The core of their analysis is based on bounding the detour that the optimal TSPN tour has to make in order to visit the centers of each disk and shows that it is at most 2Rn in the worst case. Hame, Hyytia and Hakula [2011] asked whether this bound is tight when R is small and conjectured that it is at most \sqrt{3}Rn.

In this talk, we will further investigate this question and derive structural properties of the optimal TSPN tour to describe the cases in which the bound is smaller than 2Rn. Specifically, we show that if the optimal TSPN tour is not a straight line, at least one of the following is guaranteed to be true: the bound is smaller than 2Rn or the TSP on the centers is a 2-approximation (best we can get with this heuristic). This leads to an improved overall approximation factor for the problem. Along the way, we will uncover ways in which the TSPN problem is structurally different from the classical TSP.

##
19.12.18, Matya Katz, BGU: Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains

**Wednesday, December 19th, 2018, 16:10**

**Abstract:**

A graph G = (V,E) is terrain-like if one can assign a unique integer from the range [1..|V|] to each vertex in V, such that, if both {i,k} and {j,l} are in E, for i < j < k < l, then so is {i,l}. We present a local-search-based PTAS for minimum dominating set in terrain-like graphs. Then, we observe that, besides the visibility graphs of x-monotone terrains which are terrain-like, so are the visibility graphs of weakly-visible polygons and weakly-visible terrains, immediately implying a PTAS for guarding the vertices of such a polygon or terrain from its vertices. We also present PTASs for continuously guarding the boundary of a WV-polygon or WV-terrain, either from its vertices, or, for a WV-terrain, from arbitrary points on the terrain. Finally, we compare between terrain-like graphs and non-jumping graphs (Ahmed et al., 2017), answering a question concerning the latter family, and observing that both families admit PTASs for maximum independent set.

##
26.12.18, Ravid Cohen, TAU: Maintaining the union of unit discs under insertion with near-optimal overhead

**Wednesday, December 26th, 2018, 16:10**

**Abstract:**We present efficient data structures for problems on unit discs and arcs of their boundary in the plane. (i) We give an output-sensitive algorithm for the dynamic maintenance of the union of $n$ unit discs under insertions in $O(k \log^2 n)$ update time and $O(n)$ space, where $k$ is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. (ii) As part of the solution of (i) we devise a fully dynamic data structure for the maintenance of lower envelopes of pseudo-lines, which we believe is of independent interest. The structure has $O(\log^2 n)$ update time and $O(\log n)$ vertical ray shooting query time. To achieve this performance, we devise a new algorithm for finding the intersection between two lower envelopes of pseudo-lines in $O(\log n)$ time, using \emph{tentative} binary search. (iii) We also present a dynamic range searching structure for a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), where the ranges are unit discs, with $O(n \log n)$ preprocessing time, $O(n^{1/2+\varepsilon} + \ell)$ query time and $O(\log^2 n)$ amortized update time, where $\ell$ is the size of the output and for any $\varepsilon>0$. The structure requires $O(n)$ storage space.

This is joint work with Pankaj K. Agarwal, Dan Halperin, and Wolfgang Mulzer

##
02.01.19, Sariel Har-Peled, UIUC, Haim Kaplan, TAU: On Locality-Sensitive Orderings and Their Applications

**Wednesday, January 2nd, 2019, 16:10**

**Abstract:**

For any constant d and parameter ε>0, we show the existence of (roughly) 1/ε^d orderings on the unit cube [0,1)^d, such that any two points p,q∈[0,1)^d that are close together under the Euclidean metric are “close together” in one of these linear orderings in the following sense: the only points that could lie between p and q in the ordering are points with Euclidean distance at most ε∥p−q∥ from p or q. These orderings are extensions of the Z-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in low-dimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search.

Joint work with Timothy M. Chan and Mitchell Jones

##
09.01.19, Shiri Artstein-Avidan, TAU, Haim Kaplan, TAU: On Radial Isotropic Position: Theory, Algorithms, and Applications

**Wednesday, January 9th, 2019, 16:10**

**Abstract:**We review the theory of, and develop algorithms for transforming a finite point set in $\R^d$ into a set in \emph{radial isotropic position} by a nonsingular linear transformation followed by rescaling each image point to the unit sphere. This problem arises in several applications, such as obtaining a linear lower bound on the unbounded error probabilistic communication complexity, robust subspace recovery in the presence of outliers in machine learning, and a recent application of Kane et al. to point location in arrangements of hyperplanes in high dimensions. We study the algorithmic issues in finding the transformation that puts a dataset in radial isotropic position, and design efficient algorithms that are based on gradient descent, applied to a particular convex function whose minimum defines the transformation (which, when it exists, is unique up to rotation). We show that computing the gradient amounts to computing the Singular Value Decomposition (SVD) of a certain matrix associated with the input set, so this technique is simple to implement. Our main contribution is an analysis of the convergence rates of several variants of the gradient descent technique, when applied to our function. Interestingly, the SVD also plays a crucial role in the analysis.

Joint work with Micha Sharir

##
23.01.19, Csaba D. Toth, CSUN: Weak Embeddings and Crossing Minimization

**Wednesday, January 23rd, 2019, 16:10**

**Abstract:**An embedding $\varphi:G\rightarrow M$ of a graph $G$ into a 2-manifold $M$ maps the vertices in $V(G)$ to distinct points and the

edges in $E(G)$ to interior-disjoint Jordan arcs between the corresponding vertices. Due to data compression or low resolution,

nearby vertices and edges of a graph drawing may be bundled to a common node or arc. This raises the computational problem of deciding whether a

given map $\varphi:G\rightarrow M$ corresponds comes from an embedding.

A map $\varphi:G\rightarrow M$ is a weak embedding if it can be perturbed into an embedding $\psi_\varepsilon:G\rightarrow M$ with

$\|\varphi-\psi_\varepsilon\|<\varepsilon$ for every $\varepsilon>0$.

We present an $O(n\log n)$-time algorithm that recognizes weak embeddings: It performs a sequence of local operations that gradually

“untangles” the image $\varphi(G)$ into an embedding $\psi(G)$, or reports that $\varphi$ is not a weak embedding. Similar local operations

can also be used for perturbing a given map $\varphi:G\rightarrow M$ into a proper drawing that minimizes the number of crossings when $G$ is

a cycle and the map $\varphi$ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). However, crossing

minimization is NP-complete (i) when $G$ is an arbitrary graph and $\varphi$ has no spurs, and (ii) when $\varphi$ may have spurs and $G$

is a cycle or a union of disjoint paths.

Joint work with Hugo Akitaya and Radoslav Fulek

##
06.03.19, Bettina Speckmann, TU Eindhoven: Agglomerative Clustering of Growing Squares: Theory and Practice

**Wednesday, March 6th, 2019, 16:10**

**Abstract:**We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs.

We present a fully dynamic kinetic data structure that maintains a set of n disjoint growing squares. Our data structure uses O(n (\log n \log\log n)^2) space, supports queries in worst case O(\log^2 n) time, and updates in O(\log^5 n) amortized time. This leads to an O(n\alpha(n)\log^5 n) time algorithm to solve the agglomerative clustering problem, which significantly improves upon the current best O(n^2) time algorithms.

From a practical point of view, our new algorithm does not perform better than the naive algorithms for n < 10^6. We hence also present an alternative agglomerative clustering algorithm which works efficiently in practice. Our algorithm relies on the use of quadtrees to speed up spatial computations. Interestingly, even in non-pathological datasets, we can encounter large glyphs that intersect many quadtree cells and that are involved in many clustering events. We therefore devise a special strategy to handle such large glyphs. We test our algorithm on several synthetic and real-world datasets and show that it performs well in practice.

Joint work with Thom Castermans, Frank Staals, and Kevin Verbeek

##
13.03.19, Aviv Tamar, The Technion: Learning to plan

**Wednesday, April 3rd, 2019, 16:10**

**Abstract:**Motion planning is fundamental to almost all robotic applications deployed today. However, for domains where the environment can change rapidly, such as in e-commerce applications or home robotics, it is desired to plan *fast*, and the computational burden of conventional planning algorithms can be limiting.

Recent developments in deep learning demonstrated learning of complex patterns in data for various decision making domains such as computer vision, protein folding, and games. Motivated by these successes, we ask — can we use deep learning to approximate a planning computation? In such a scheme, learning offline on a set of training problems would allows us to solve similar problems at test time faster, using the neural network’s prediction.

We begin by investigating the capacity of deep networks to represent a planning computation. We show that the classic value iteration algorithm is equivalent to a certain type of convolutional network, and exploit this idea to design the value iteration network — a differentiable planner that can be trained using supervised learning or reinforcement learning.

Then, we show how deep learning can be used to improve discrete task planning, by learning powerful image-based heuristic functions for A* search. We conclude with recent work on learning for continuous motion planning. Here, the key is in the learning algorithm — we find that learning to navigate tight passages is fundamentally challenging for supervised learning approaches. We instead propose a novel reinforcement learning algorithm that exploits features of the motion planning problem to effectively learn a neural motion planner. We demonstrate predicting motion plans with almost perfect accuracy on a 4-dimensional robotic arm domain with challenging narrow passages.

##
20.03.19, **EuroCG, no seminar**

**EuroCG, no seminar**

##
03.04.19, Esther Ezra, BIU: An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

**Wednesday, April 3rd, 2019, 16:10**

**Abstract:**n 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in R^d and if D\geq 1 is an integer, then there is a d-variate polynomial P of degree at most D so that each connected component of R^d \setminus Z(P) intersects O(n/D^{d-g}) sets from S (where Z(p) is the zero set of P). Such a polynomial is called a “generalized partitioning polynomial”. We present a randomized algorithm that computes such polynomials efficiently—the expected running time of our algorithm is linear in |S|. Our approach exploits the technique of quantifier elimination combined with that of \epsilon-samples.

We present several applications of our result including data structures that support point-enclosure queries, range search queries, and vertical ray-shooting queries among semi-algebraic sets in R^d.

Joint work with Pankaj Agarwal, Boris Aronov, and Josh Zahl

##
10.04.19, Orit Raz, UBC: Every embedding of a dense graph has a rigid subset

**Wednesday, April 10th, 2019, 16:10**

**Abstract:**While the problem of determining whether an embedding of a graph G in R^2 is infinitesimally rigid is well understood, specifying whether a given embedding of G is rigid or not is still a hard task that usually requires ad hoc arguments.

In the talk I will discuss a recent result (joint with Jozsef Solymosi), where we show that every embedding of a sufficiently dense graph has a rigid subset. The proof uses a reduction of the original rigidity problem to a question about line configurations in R^3.

##
15.05.19, Rom Pinchasi, The Technion: Algebraic context of some geometric problems

**Wednesday, May 15th, 2019, 16:10**

**Abstract:**We draw an algebraic point of view of some classical geometric problems about points and lines in the plane. We will present both a polynomial approach and a classical algebraic geometry approach (following Green and Tao paper on the number of ordinary lines). Many interesting open problems as well as some results and partial results will be combined in the talk.

Based on on-going joint research with Haya Keller, and with Eyal Ackerman.

##
29.05.19, Shakhar Smorodinsky, BGU: Conflict-Free coloring of String Graphs

**Wednesday, May 29th, 2019, 16:10**

**Abstract:**Given a graph $G=(V,E)$ and a fixed integer $k >1$, a coloring of the vertices of $G$ is called k-Conflict-Free (kCF in short) if for any vertex $v$ there exists at least one color that is assigned to at least one and at most $k$ of its neighbors. (there are two versions of the notion of neighborhood: open where it is the set $N(v)$ of all neighbors of $v$ or closed which is ${v} \cup N(v)$.

For $k=1$ such colorings have been studied extensively. In particular by J. Pach, G. Tardos, by P. Cheilaris, by Z. Abel, V. Alvarez, E.. Demaine, S. Fekete, A. Gour, A. Hesterberg, P. Keldenich, C. Scheffer and by R. Glebov, T. Sz\'{a}bo and G. Tardos for general graphs.In this talk we focus on string graphs. That is, intersection graphs of simple Jordan curves in the plane.

Joint work with Chaya Keller and Alexandre Rok

##
05.06.19, Michal Kleinbort, TAU: Sampling-based robot motion planning: The common bottlenecks and a novel asymptotically optimal planner

**Wednesday, Jun 5th, 2019, 16:10**

**Abstract:**The ability to plan collision-free motions is an important aspect of robots’ autonomy: While performing tasks in cluttered environments, the robots need to avoid obstacles as well as fellow robots. The motion-planning problem has been extensively studied over the past four decades. It was primarily investigated as a theoretical problem in computational geometry and has since been the subject of research in robotics as well as computer graphics, computational biology, architectural design, artificial intelligence, and more.

In this talk, I will present results developed during my PhD studies concerning the currently most common type of motion planning algorithms—sampling-based motion planners—and their main building blocks, namely collision detection and nearest-neighbor search. I will discuss the relation between these two components, theoretically and practically, and show that the distribution of work between them defies common belief.

Motion planning can be notoriously challenging when additional constraints are taken into account. For instance, when the robots have differential (kinodynamic) constraints on their motion, specialized planning algorithms, often different from their geometric counterparts, are applied. In my talk, I will also present our ongoing efforts to devise a simple kinodynamic planner that efficiently finds high-quality paths with high probability.

The talk is based on work developed with my advisor Prof. Dan Halperin, in collaboration with Kiril Solovey, Oren Salzman, Kostas Bekris, Zakary Littlefield, and Riccardo Bonalli.

##
12.06.19, Omer Gold, TAU: Diameter spanners

**Wednesday, June 12th, 2019, 16:10**

**Abstract:**The diameter of a graph is one if its most important parameters, being used in many real-word applications. In particular, the diameter dictates how fast information can spread throughout data and communication networks. Designing such networks with a sparse (subquadratic) set of edges and small diameter is highly desired.

Thus, it is a natural question to ask how much can we sparsify a graph while guaranteeing that its diameter is preserved within an approximation factor $t$, for some $t>1$.

To tackle this question, we initiate the study of diameter spanners. Given a directed graph $G = (V, E)$, a subgraph $H = (V, E’ \subseteq E)$ is defined to be a $t$-diameter spanner if the diameter of $H$ is at most $t$ times the diameter of $G$.

We show the existence of (and algorithms to compute) various $t$-diameter spanners with a sparse set of edges and $t<2$, for directed unweighted graphs.

We also give diameter spanner constructions for directed graphs with edge-weights that are at least $1$.

Joint work with Keerti Choudhary

##
03.07.19, Kiril Solovey, Stanford: Scalable and Congestion-aware Routing for Autonomous Mobility-On-Demand via Frank-Wolfe Optimization

**Wednesday, July 3rd, 2019, 16:10**

**Abstract:**We consider the problem of vehicle routing for Autonomous Mobility-on-Demand (AMoD) systems, wherein a fleet of self-driving vehicles provides on-demand mobility in a given environment. Specifically, the task it to compute routes for the vehicles (both customer-carrying and empty travelling) so that travel demand is fulfilled and operational cost is minimized. The routing process must account for congestion effects affecting travel times, as modeled via a volume-delay function (VDF). Route planning with VDF constraints is notoriously challenging, as such constraints compound the combinatorial complexity of the routing optimization process. Thus, current solutions for AMoD routing resort to relaxations of the congestion constraints, thereby trading optimality with computational efficiency.

In this paper, we present the first computationally-efficient approach for AMoD routing where VDF constraints are explicitly accounted for. We demonstrate that our approach is faster by at least one order of magnitude with respect to the state of the art, while providing higher quality solutions. From a methodological standpoint, the key technical insight is to establish a mathematical reduction of the AMoD routing problem to the classical traffic assignment problem (a related vehicle-routing problem where empty traveling vehicles are not present). Such a reduction allows us to extend powerful algorithmic tools for traffic assignment, which combine the classic Frank-Wolfe algorithm with modern techniques for pathfinding, to the AMoD routing problem. We provide strong theoretical guarantees for our approach in terms of near-optimality of the returned solution.

This is joint work with Mauro Salazar and Marco Pavone. To appear in Robotics: Science and Systems 2019.

##
07.07.19, Omer Gold, TAU: New algorithms for some classical problems in P

**Sunday, July 7th, 2019, 16:10**

**Abstract:**The search for optimal algorithms is at the core of computer science since its emergence as a field. Yet for the majority of the studied problems we do not know whether state-of-the-art algorithms are the best possible.

Among the most popular problems in P are those that have standard algorithms that run in quadratic time or cubic time, such as 3SUM (quadratic time) and All-Pairs-Shortest-Paths (cubic time). Quadratic-time algorithms are also used in solving many basic matching problems between strings, curves, and point-sequences. In this thesis, we present improved algorithms and decision trees for the following core problems.

1) Improved decision tree for k-SUM and improved subquadratic-time algorithm for 3SUM.

2) The first subquadratic-time algorithms for computing Dynamic Time Warping and Geometric Edit Distance between two point-sequences on the line, breaking the 50-year old quadratic time barrier of these problems. Our algorithms work also for higher dimensions, when the underlying metric is polyhedral.

3) The first strongly-polynomial subcubic algorithm for computing high-dimensional closest pair under the L-infinity metric.

4) Showing that every directed unweighted graph has various subgraphs of subquadratic size that preserve the diameter of the original graph within an approximation factor less than 2. We call these subgraphs “diameter spanners”, and we show efficient algorithms to construct them.

The talk is based on work developed as part of my Ph.D. studies under the supervision of Prof. Micha Sharir.

##
03.01.18, Gabriel Nivasch, Ariel: Grid peeling and the affine curve-shortening flow

**Wednesday, January 3rd, 2018, 16:10**

**Abstract:**Experimentally, the convex-layer decomposition of subsets of the integer grid (“grid peeling”) seems to behave at the limit like the affine curve-shortening flow. We offer some theoretical arguments to explain this phenomenon. In particular, we derive some rigorous results for the special case of peeling the quarter-infinite grid: We prove that, in this case, the number of grid points removed up to iteration n is Theta(n^(3/2)log n), and moreover, the boundary at iteration n is sandwiched between two hyperbolas that are separated from each other by a constant factor.

Joint work with David Eppstein and Sariel Har-Peled

##
10.01.18, Natan Rubin, BGU: Further consequences of the colorful Helly hypothesis

**Wednesday, January 10th, 2018, 16:10**

**Abstract:**Let $\F$ be a family of convex sets in $\reals^d$, which are colored with $d+1$ colors.

We say that $\F$ satisfies the Colorful Helly Property if every rainbow selection of $d+1$ sets, one set from each color class,has a non-empty common intersection. The Colorful Helly Theorem of Lovász states that for any such colorful family $\F$ there is a color class $\F_i\subset \F$, for $1\leq i\leq d+1$, whose sets have a non-empty intersection. We establish further consequences of the Colorful Helly hypothesis. In particular, we show that for each dimension $d\geq 2$ there exist numbers $f(d)$ and $g(d)$ with the following property: either one can find an additional color class whose sets can be pierced by $f(d)$ points, or all the sets in $\F$ can be crossed by $g(d)$ lines.

Joint work with Leonardo Martinez and Edgardo Roldan-Pensado.

##
17.01.18, **No seminar**

**No seminar**

##
07.03.18, Kiril Solovey, TAU: Multi-robot motion planning: theory and practice

**Wednesday, March 7th, 2018, 16:10**

**Abstract:**Motion planning is a fundamental problem in robotics concerned with allowing autonomous robots to efficiently navigate in environments cluttered with obstacles. Although motion planning has originated as a strictly theoretical problem in computer science, it is applied nowadays in various fields such as computational biology, computer graphics, and most naturally robotics. Unfortunately, motion planning is notoriously challenging—both theoretically and practically—and many aspects of the problem are not sufficiently understood, even after 30 years of extensive multidisciplinary research.

In this talk I will present results developed during my PhD studies concerning various algorithmic aspects of motion planning. I will put special emphasis on multi-robot systems, which pose a great challenge due to their high-dimensional search space. In the second part of the talk I will present several new results on the theoretical foundations of sampling-based planners, which are extensively used in practice.

The talk is based on work developed with my advisor Prof. Dan Halperin. Part of the contributions that will be presented are a result of collaboration with Oren Salzman, Michal Kleinbort, Aviel Atias, Mark de Berg, Aviv Adler, Jingjin Yu, Or Zamir, Rahul Shome, Andrew Dobson, and Kostas Bekris.

##
14.03.18, Pankaj K. Agarwal, Duke University: Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon

**Wednesday, March 14th, 2018, 16:10**

**Abstract:**We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set S of n point sites in a static simple polygon P with m vertices. Our data structure allows us to insert a new site in S, delete a site from S, and ask for the site in S closest to an arbitrary query point q ∈ P. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in P. Our data structure achieves polylogarithmic update and query times, and uses O(npolylog(n)+ m) space. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists and can be computed efficiently.

Joint work with Lars Arge and Frank Staals

##
11.04.18, Esther Ezra, Bar-Ilan University: Constructive Polynomial Partitioning for Lines in~$\reals^3$: Revisiting Depth Cycle Elimination

**Wednesday, April 11th, 2018, 16:10**

**Abstract:**A recent extension of Guth (2015) to the basic polynomial partitioning technique of Guth and Katz (2015) shows the existence of a partitioning polynomial, for a given set of $k$-dimensional varieties in ${\reals}^d$, which subdivides space into open cells each of which meeting only a small fraction of the total number of varieties. For most instances, it is unknown how to obtain an explicit representation of such a partitioning polynomial (and how to construct it efficiently). This, in particular, applies to the (simple) case of lines in $3$-space. In this work we present an efficient algorithmic (but somewhat suboptimal) construction for this setting, under the assumption that the lines are non-vertical and pairwise disjoint. We then revisit the problem of eliminating depth cycles among $n$ non-vertical pairwise disjoint triangles in $3$-space, recently been studied by Aronov etal. (2017) and de Berg (2017). Our main result is an algorithmic $O(n^{5/3+\eps})$ bound, for any $\eps > 0$, on the number of pieces one needs to cut the triangles such that the depth relation they induce does not contain cycles. The running time of our algorithm is comparable with this combinatorial bound.

Joint work with Boris Aronov.

##
02.05.18, Natan Rubin, Ben Gurion University: "An improved bound for weak epsilon nets in the plane

**Wednesday, May 2nd, 2018, 16:10**

**Abstract:**We show that for any set $P$ of $n$ points in the plane and $\eps>0$ there exists a set of $O(1/\eps^{1.5+\gamma})$ points in the plane, for any \gamma>0, that pierce every convex set $K$ containing at least $\eps |P|$ points of P. This is the first improvement of the 1992 upper bound $O(1/eps^2)$ of Alon, Bárány, Füredi, and Kleitman.

##
16.05.18, Janos Pach, Rényi Institute, Budapest and EPFL, Lausanne: New Crossing Lemmas

**Wednesday, May 16th, 2018, 16:10**

**Abstract:**The Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi (1982) and Leighton (1983) states that if a graph of n vertices and e>4n edges is drawn in the plane, then the number of crossings between its edges must be at least constant times e^3/n^2. This statement, which is asymptotically tight, has found many applications in combinatorial geometry and in additive combinatorics. However, most results that were obtained using the Crossing Lemma do not appear to be optimal, and there is a quest for improved versions of the lemma for graphs satisfying certain special properties. In this talk, I describe some recent extensions of the lemma to multigraphs (joint work with G. Tóth).

##
30.05.18, Chen Ziv, TAU: On the Complexity of k-Level in Arrangements of Planes

**Wednesday, May 30th, 2018, 16:10**

**Abstract:**A k-set of a finite point set S in the Euclidean plane is a subset of k elements of S that can be strictly separated from the remaining points by a line. We discuss the problem of bounding the complexity of the number of k-sets in a set of n points. This problem was first studied by Lovász in 1971 and by Erdős et al. in 1973. It is an open problem to bound the complexity of the number of k-sets, and there is a big gap between the lower bound and the upper bound known today. This problem has many versions and generalizations, which some of them we introduce.

We discuss a dual version of the problem in R^3: let A be a set of n non-vertical planes in R^3, in general position. We say that a point p lies at level k of the arrangement of A, if exactly k planes of A pass below p. Our goal is to obtain an upper bound on the complexity of the k-level of the arrangement of A. We introduce a dual version of a technique, setting and bounds that are based on a simple version of a result presented in “An improved bound for k-sets in three dimensions” by Sharir, Smorodinsky and Tardos (1999), and show a known upper bound of O(nk^(5/3)).

Our work is in progress, and the goal is to generalize the result we show here for more complicated collection of objects.

##
06.06.18, Noam Solomon, Harvard: Extremal subsets of the boolean cube with respect to projections

**Wednesday, January 11th, 4:10pm Tel Aviv time (3:10 pm CET, 9:10am NY time)**

**Evanthia Papadopoulou, Università della Svizzera italiana**

**Abstract:**

diagrams of segments, circles, polygons, or clusters of points in the

plane, are sometimes overlooked or underestimated. As a result some

basic questions concerning the latter diagrams may surprisingly remain

open to date. In this talk I will discuss Voronoi-like graphs as a tool

towards addressing such problems.

A Voronoi-like graph is a relaxed Voronoi structure, defined as a graph

on the arrangement of a given bisector system. In a Voronoi-like graph,

a vertex v and its incident edges, within a small neighborhood around v,

must appear in a Voronoi diagram of three sites. For points in the

Euclidean plane, where the bisector system forms a line arrangement, a

Voronoi-like graph always coincides with the Voronoi diagram of the

involved sites. How about bisector systems which are not lines (nor

pseudolines), such as those related to line-segments, or more generally,

to abstract Voronoi diagrams? I will answer this question in this talk

and give examples of simple expected linear-time algorithms to compute

Voronoi-like trees (or forests). Examples include updating an abstract

Voronoi diagram after deletion of one site, updating a constraint

Delaunay triangulation after inserting a new segment constraint, and

others. As a byproduct, I will also discuss a simple alternative to

backwards analysis applicable to order-dependent structures.

Some parts of this talk is joint work with Kolja Junginger.