Search
Close this search box.

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

Wednesday, January 17th, 4:10pm Tel Aviv time (3:10pm CET)

Wednesday, January 24th, 4:10pm Tel Aviv time (3:10pm CET)

Monday, January 29th, 6:00pm Tel Aviv time (5:00pm CET)   (Zoom)

Wednesday, February 7th, 4:10pm Tel Aviv time (3:10pm CET) 

Wednesday, February 14th, 4:10pm Tel Aviv time (3:10pm CET) 

Monday, February 19th, 6:00pm Tel Aviv time (5:00pm CET) (Zoom)

Monday, February 26th, 5:10pm Tel Aviv time (4:10pm CET) (in person and Zoom)

Monday, March 4th, 6:00pm Tel Aviv time (5:00pm CET) (Zoom)

Wednesday, March 13th, 4:10pm Tel Aviv time (3:10pm CET)

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

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. 

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.

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.

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.

Paper: https://arxiv.org/abs/2106.02335

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.)

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/

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

Evanthia Papadopoulou, Università della Svizzera italiana

Abstract:

Differences between classical Voronoi diagrams of points, versus Voronoi

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.

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.

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.

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.

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.

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.

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 

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

twisting a nut on a bolt or pulling a nail with a hammer claw, requires
enabling reasoning over interlocking force and motion constraints over discrete
and continuous choices. I categorize forceful manipulation as tasks where
exerting substantial forces is necessary to complete the task. While all
actions with contact involve forces, I focus on tasks where generating and
transmitting forces is a limiting factor of the task that must be reasoned over
and planned for. I’ll first formalize constraints for forceful manipulation
tasks where the goal is to exert force, often through a tool, on an object or
the environment. These constraints define a task and motion planning problem
that we solve to search for both the sequences of discrete actions, or
strategy, and the continuous parameters of those actions.
 
This talk will primarily discuss two papers (IROS 2019, ICRA 2021) as well as
ongoing work. All work is done in collaboration with my two advisors, Tomás
Lozano-Pérez and Alberto Rodriguez. 

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).

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.

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.

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.

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$.

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.

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

Abstract:

Let T be a set of n triangles in 3-space, and let \Gamma be a family of
algebraic arcs of constant complexity in 3-space. We show how to preprocess T
into a data structure that supports various \emph{intersection queries} for
query arcs \gamma \in \Gamma, such as detecting whether \gamma intersects any
triangle of T, reporting all such triangles, counting the number of
intersection points between \gamma and the triangles of T, or returning the
first triangle intersected by a directed arc \gamma, if any (i.e., answering
arc-shooting queries). Our technique is based on polynomial partitioning and
other tools from real algebraic geometry, among which is the cylindrical
algebraic decomposition.
 
Our first result is an O^*(n^{4/3})-size data structure that answers a query in
O^*(n^{2/3}) time. Next, we devise an O^*(n)-size data structure that answers a
query in O^*(n^{4/5}) time. Incorporating this structure at the leaf nodes of
the main structure reduces its overall size to O^*(n^{11/9}), without affecting
its query time which remains O^*(n^{2/3}). We also present a data structure
that provides a trade-off between the query time and the size of the data
structure. For example, if \Gamma is a family of algebraic arcs defined by t > 1
real parameters, increasing the storage to O^*(n^{3/2}) decreases the query
time to O^*(n^{\rho}), where \rho=\max {1/2, (2t-3)/3(t-1)} < 2/3. We also show
that this query time can be further improved for circular query arcs.
 
Our approach can be extended to many other intersection-searching problems in
three and higher dimensions. We exemplify this versatility by giving an
efficient data structure for answering segment-intersection queries amid a set
of spherical caps in 3-space, and we lay a roadmap for extending our approach
to other intersection-searching problems.
 
Joint work with Pankaj Agarwal, Boris Aronov, Matya Katz, and Micha Sharir.

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

Abstract:

In this talk we will learn what visual transformers are and how they can be employed in order to significantly speed up sampling-based motion planning.

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.

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.

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

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

Wednesday, June 15th, 4:10pm
CheckPoint 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.

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

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.

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

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.

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.

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.

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.

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

Recording

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.

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.

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.

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

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.

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.

Wednesday, December 11th, 2019, 16:10

Checkpoint 480

Abstract:

We define and study a discrete process that generalizes the convex-layer decomposition (a.k.a. “onion decomposition”) of a planar point set. Our process, which we call “homotopic curve shortening” (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P of point obstacles, and evolves in discrete steps, where each step consists of taking shortcuts around the obstacles and reducing the curve to its shortest homotopic equivalent.


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

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

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.

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:

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

Recording:
Zoom

Presentation:
PowerPoint

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.

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. 

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.

 
In this paper we show that even an utterly simple variant of the connected-assembly-partitioning problem is hard: Given a connected set A of unit squares in the plane, each contained in a distinct cell of a uniform grid, find a subset S of A that can be rigidly translated to infinity along a prescribed direction, such that both subassemblies S and A\S are each connected, and such that S does not collide with A\S throughout the motion. We show that this problem is NP-Complete, and by that settle a long-standing open problem posed by Wilson et al (1995) a quarter of a century ago. This motivates us to look for efficient solutions in special cases, which we describe here as well.  
 
Joint work with Pankaj K. Agarwal, Boris Aronov, and Dan Halperin.
 

 

Wednesday, May 5th, 2020, 16:10

Abstract:

I will present a joint work with Emo Welzl, in which we study order
types of points in general position in the plane (realizable simple
planar order types, realizable uniform acyclic oriented matroids of
rank 3). We establish the following two main results:
 
– The number of extreme points in an n-point order type, chosen
 uniformly at random from all such order types, is on average
 4+o(1). For labeled order types, this number has average
 exactly 4-8/(n^2-n+2) and variance at most 3.
 
– The (labeled) order types read off a set of n points sampled
 independently from the uniform measure on a convex planar domain,
 smooth or polygonal, or from a Gaussian distribution are
 concentrated, i.e. such sampling typically encounters only a
 vanishingly small fraction of all order types of the given size.
 
The results on unlabeled order types depend on characterizing the
possible groups of orientation preserving bijections of an antipodal,
finite subset of the 2-dimensional sphere. We prove that any such
group must be cyclic, dihedral or one of A_4, S_4 or A_5 (and each
case is possible). These are the finite subgroups of SO(3) and our
proof follows the lines of their characterization by Felix Klein.
 

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

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.

 
We consider an extension of 3SUM where A, B, C, are three sets of points in the plane, and the sum function is replaced by a polynomial function of constant degree. This results in a family of problems referred to as “3POL”. A central problem in this family is the so-called “collinearity testing” – one of the basic 3SUM-hard problems in computational geometry.
In this talk I will present several 3POL problems, including a few special cases of collinearity testing. I will describe subquadratic solutions for these problems in the algebraic decision tree model, these solutions are based on the polynomial partitioning method of Guth and Katz. 
 
Joint work with Boris Aronov and Micha Sharir.

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.”

Joint work with Jeff Erickson and Junyan Xu.

Recordings:
Zoom meeting

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.  

We study the following yet more general notion: Let $H=(V,E)$ be a hypergraph $0 < \epsilon \leq 1$ a real and $t \geq 1$ an integer.
We call a family $N$ of subsets (of $V$) of cardinality $t$ an {\em $\epsilon-t$-net} if every hyperedge $S \in E$ with size at least $\epsilon |V|$  contains at least one set from $N$. When $t=1$ this is the classical notion of $\epsilon$-net.
We show that for any constant integers $t,d$ any hypergraph with VC-dimension $d$ admits an $\epsilon-t$-net of size $O(\frac{d}{\epsilon} \log \frac{1}{\epsilon})$.
Joint work with Noga Alon, Bruno Jartoux, Chaya Keller and Yelena Yuditsky.

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:

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

Recording:
Zoom

Presentation:
PowerPoint

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.

 

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:

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

Recording:
Zoom

Presentation:
PowerPoint

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.

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

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.

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.

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

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

https://arxiv.org/abs/1809.11147

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

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

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

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.

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

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.

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.

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

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.

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 

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. 

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.

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

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.

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.

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

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.

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.

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).

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.

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

Evanthia Papadopoulou, Università della Svizzera italiana

Abstract:

Differences between classical Voronoi diagrams of points, versus Voronoi

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.

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content