06.01.21, Alex Steiger, Duke University: Decomposing the complement of the union of cubes
Wednesday, January 6th, 16:10Abstract: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 […]
02.12.20, Elon Rimon, Technion: Configuration space perspectives on minimalistic robot hands and a caging-based biohazard sample handling robot
Wednesday, December 2nd, 16:10Abstract:Ten years of research on minimalistic robot hands resulted in novel robot handdesigns and culminated in a new book, The Mechanics of Robotic Grasping byRimon and Burdick. Perspectives gained from this activity will be shared in a talkthat will consist of two related parts. Part I describes the configuration space analysisof multi-finger grasps. […]
09.12.20, Omrit Filtser, SUNY Stony Brook: Static and streaming data structures for Fréchet distance queries
Wednesday, December 9th, 16:10Abstract: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 […]
16.12.20, Sándor Fekete, TU Braunschweig: Geometric algorithms for large robot swarms
Wednesday, December 16th, 16:10Abstract: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 challengesarise 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 […]
23.12.20, Tzvika Geft, TAU: Algorithms for two-handed planar assembly partitioning with connectivity constraints
Wednesday, December 23rd, 16:10Abstract: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 […]
30.12.20, Esther Ezra, Bar Ilan University: On ray shooting amid triangles in three dimensions and related problems
Wednesday, December 30th, 16:10Abstract: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 […]
04.11.20, Sariel Har-Peled, UIUC: Reliable spanners
Wednesday, November 4th, 16:10Abstract:A spanner is reliable if it can withstand large catastrophicfailures in the network. More precisely, any failure of some nodes canonly cause a small damage in the remaining graph in terms of thedilation. That is, the spanner property is maintained for almost allthe nodes in the residual graph. We will discuss recent […]
11.11.20, Wolfgang Mulzer, FU Berlin: Long alternating paths exist
Wednesday, November 11th, 16:10Abstract:Let P be a set of 2n points in convex position, such that npoints are colored red and n points are colored blue. A non-crossingalternating path on P of length l is a sequence p_1, …, p_l of lpoints from P so that (i) all points are pairwise distinct; (ii) any twoconsecutive […]
18.11.20, Irina Kostitsyna, TU Eindhoven: Multi-robot motion planning for disc robots
Wednesday, November 18th, 16:10Abstract: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 […]
25.11.20, Florian Pokorny, KTH Royal Institute of Technology: Some methods for reasoning about topology & global geometry in machine learning & robotics
Wednesday, November 25th, 16:10Abstract:In this talk, I will discuss some applications of ideas from topologicaldata analysis based on the use of Delaunay-Cech and Alpha complexes.Use cases in robotics include motion clustering as well as applicationsto motion planning, caging/path non-existence and the analysis ofconfiguration spaces, while applications to machine learning include theclassification and topological data analysis […]