30.05.18, Chen Ziv, TAU: On the Complexity of k-Level in Arrangements of Planes
Wednesday, May 30th, 2018, 16:10Abstract: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. […]
06.06.18, Noam Solomon, Harvard: Extremal subsets of the boolean cube with respect to projections
Wednesday, January 11th, 4:10pm Tel Aviv time (3:10 pm CET, 9:10am NY time)Evanthia Papadopoulou, Università della Svizzera italianaAbstract:Differences between classical Voronoi diagrams of points, versus Voronoidiagrams of segments, circles, polygons, or clusters of points in theplane, are sometimes overlooked or underestimated. As a result somebasic questions concerning the latter diagrams may surprisingly remainopen to date. […]
07.03.18, Kiril Solovey, TAU: Multi-robot motion planning: theory and practice
Wednesday, March 7th, 2018, 16:10Abstract: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. […]
14.03.18, Pankaj K. Agarwal, Duke University: Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon
Wednesday, March 14th, 2018, 16:10Abstract: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 […]
11.04.18, Esther Ezra, Bar-Ilan University: Constructive Polynomial Partitioning for Lines in~$reals^3$: Revisiting Depth Cycle Elimination
Wednesday, April 11th, 2018, 16:10Abstract: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 […]
02.05.18, Natan Rubin, Ben Gurion University: “An improved bound for weak epsilon nets in the plane
Wednesday, May 2nd, 2018, 16:10Abstract: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 […]
16.05.18, Janos Pach, Rényi Institute, Budapest and EPFL, Lausanne: New Crossing Lemmas
Wednesday, May 16th, 2018, 16:10Abstract: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. […]
03.01.18, Gabriel Nivasch, Ariel: Grid peeling and the affine curve-shortening flow
Wednesday, January 3rd, 2018, 16:10Abstract: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, […]
10.01.18, Natan Rubin, BGU: Further consequences of the colorful Helly hypothesis
Wednesday, January 10th, 2018, 16:10Abstract: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 […]