(Virtual) Discrete & Computational Geometry Day
in Memory of Eli Goodman and Ricky Pollack
founding editors of D&CG
co-founders of this seminar
Organized by Springer, NYU, and CUNY

Tuesday, April 12, 2022, 12:30–16:05 ET (New York time)
Zoom link: https://springer.zoom.us/j/6440052748
A shiny flyer
A YouTube playlist of video recordings of the meeting

Program:
12:30 Welcome & Introduction
12:40 Andreas Holmsen (KAIST): An allowable feast
13:15 Micha Sharir (Tel Aviv University): Polynomial partitioning: The hammer and some (recent algorithmic) nails
13:50 Esther Ezra (Bar Ilan University): Recent developments on intersection searching
14:25 Xavier Goaoc (Loria, Nancy): Some questions on order types
15:00 Andrew Suk (UC San Diego): Unavoidable patterns in simple topological graphs
15:35 Sylvain Cappell (Courant Institute): Mesh matrices of graphs, of simplicial complexes and of matroids and the significance of their eigenvalues

Abstracts

Andreas Holmsen (KAIST): An allowable feast

Eli and Ricky started their collaboration more than four decades ago, and it is hard to overstate the impact they have had on the field of discrete and computational geometry. In this talk I will highlight some of their most influential results, such as their work on allowable sequences, counting polytopes, and geometric transversals.

Micha Sharir (Tel Aviv University): Polynomial partitioning: The hammer and some (recent algorithmic) nails

We quickly review the polynomial partitioning technique introduced by Guth and Katz more than 10 years ago. We review recent algorithms for constructing partitioning polynomials, and discuss several recent algorithmic applications, to range searching with semi-algebraic sets and to various other problems. We highlight two recent and related applications: to collinearity testing for point sets, and to segment concurrency in three families of disjoint segments.

Based on joint (and disjoint) work with (too) many people.

Esther Ezra (Bar Ilan University): Recent developments on intersection searching

Algebraic techniques have been extensively used in discrete and computational geometry since the early 1980's, beginning with the seminal work of Schwartz and Sharir on the piano movers problem, where they introduced techniques from real algebraic geometry. More recently, Guth and Katz introduced the polynomial partitioning technique and almost settled the classical distinct-distance conjecture. Polynomial partitioning became a central tool in solving incidence problems, as well as other main problems in discrete geometry. Very recently, efficient constructions of partitioning polynomials have led to the solution of fundamental algorithmic problems in computational geometry, including eliminating depth cycles, point location, and semi-algebraic range searching.

In this talk I will present several recent developments in the study of intersection searching - a family of problems related to range searching. I will first describe a solution to the ray-shooting problem amid triangles in 3-space, where polynomial partitioning serves as a main tool in order to obtain an efficient data structure supporting ray-shooting queries. Then, I will show an extension of this approach, which exploits additional tools in algebraic geometry, resulting in efficient data structures for detecting intersections amid flat objects in 3-space and semi-algebraic arcs.

This talk is based on several joint works with Pankaj Agarwal, Boris Aronov, Matthew Katz, and Micha Sharir.

Xavier Goaoc (Loria, Nancy): Some questions on order types

This talk will discuss order types of point sets, from the seminal contributions of Goodman and Pollack to more recent developments.

Andrew Suk (UC San Diego): Unavoidable patterns in simple topological graphs

A simple topological graph is a graph drawn in the plane so that its vertices are represented by points, and its edges are represented by non-self-intersecting arcs connecting the corresponding points, with the property that any two edges have at most one point in common. In 2003, Pach-Solymosi-Toth showed that every $n$-vertex complete simple topological graph contains a topological subgraph on $m = \Omega(\log^{1/8} n)$ vertices that is weakly isomorphic to the complete convex geometric graph on m vertices, or the complete twisted graph on $m$ vertices. Here, we improve this bound to $(\log n)^{1/4 - o(1)}$. This is joint work with Ji Zeng.

Sylvain Cappell (Courant Institute): Mesh matrices of graphs, of simplicial complexes and of matroids and the significance of their eigenvalues

We report on some recent joint work with Edward Y. Miller on the Mesh Matrices of Graphs and the significance of their eigenvalues. We also extend some of our results to Matroid settings.