Springe direkt zu Inhalt

FUB-TAU Joint Research Workshop on Optimization in Graphs and Geometry

This five-day workshop brings together researchers from Israel and Berlin to work on problems related to geometric graphs.

Time & Location

22–26.09.2019

Department of Computer Science
Tel-Aviv University

The participants

Participants

  • Pankaj K. Agarwal, Duke University
  • Dror Aiger, Google
  • Boris Aronov, New York University
  • Stav Ashur (Sher), Ben Gurion University
  • Gill Barequet, Technion
  • Gil Ben-Shachar, Technion
  • Paz Carmi, Ben Gurion University
  • Aruni Choudhary, FU Berlin
  • Kenny Chiu, FU Berlin
  • Jonas Cleve, FU Berlin
  • Esther Ezra, Bar Ilan University
  • Zvika Geft, Tel Aviv University
  • Omer Gold, Tel Aviv University
  • Danny Halperin, Tel Aviv University
  • Bruno Jean Jartoux, Ben Gurion University
  • Haim Kaplan, Tel Aviv University
  • Alexander Kauer, FU Berlin
  • Chaya Keller, Technion
  • Katharina Klost, FU Berlin
  • Kristin Knorr, FU Berlin
  • Laszlo Kozma, FU Berlin
  • Golan Levy, Tel Aviv University
  • Wolfgang Mulzer, FU Berlin
  • Orit Raz, Hebrew University
  • Liam Roditty, Bar Ilan University
  • Natan Rubin, Ben Gurion University
  • Micha Sharir, Tel Aviv University
  • Shakhar Smorodinsky, Ben Gurion University
  • Uri Stemmer, Ben Gurion University
  • Jay Tenenbaum, Tel Aviv University
  • Tom Tsabar, Tel Aviv University
  • Emo Welzl, ETH Zürich
  • Lena Yuditsky, Ben Gurion University
  • Meirav Zehavi, Ben Gurion University

Talks

Program

All talks will be held in Room 420, Checkpoint Building, Tel Aviv University Campus.

Sunday, September 22
10:30–11:00

Coffe break-in
11:00–11:50

Wolfgang Mulzer (Freie Universität Berlin)

Algorithms for disk graphs and transmission graphs–recent developments
12:00–12:50

Meirav Zehavi (Ben Gurion University)

Decompositions in UDGs and algorithmic applications in parametrized complexity
13:00–14:00 Lunch (on site)
14:00–14:30

Uri Stemmer (Ben Gurion University)

How to find a point in the convex hull
14:30–

Free time for discussion
Monday, September 23
10:30–11:00

Coffee break-in
11:00–11:50

Emo Welzl (ETH Zürich)

Bistellar and edge flip graphs of triangulations in the plane: Geometry and connectivity
12:00–12:50

Paz Carmi (Ben Gurion University)

Stabbing pairwise intersecting disks with four points
13:00–14:00 Lunch (on site)
14:00–14:30

Boris Aronov (New York University)

Bipartite diameter and other measures under translation
14:30–

Free time for discussion
Tuesday, September 24
10:30–11:00 Coffee break-in
11:00–11:40

Aruni Choudhary (Freie Universität Berlin)

No-dimensional Tverberg theorems and algorithms
11:50–12:30

Esther Ezra (Bar Ilan University)

Testing polynomials for vanishing on Cartesian products
12:30–14:00 Lunch (on your own)
14:00–14:30

Laszlo Kozma (Freie Universität Berlin)

The complexity of permuation pattern matching
14:30–

Free time for discussion
Wednesday, September 25
10:30–11:00 Coffee break-in
11:00–11:50

Pankaj K. Agarwal (Duke Universtiy)

Clustering under perturbation stability in near-linear time
12:00–12:50

Liam Roditty (Bar Ilan University)

An almost 2-approximation for all-pairs of shortest paths in subquadratic time
13:00–14:00 Lunch (on site)
14:00–14:30

Tom Tsabar (Tel Aviv University) 

Optimized synthesis of snapping fixtures
14:30–

Free time for discussion
Thursday, September 26
10:30–11:00 Coffee break-in
11:00–11:30

Shakhar Smorodinsky (Ben Gurion Univeristy)

An optimal extension of epsilon-nets for hypergraphs with bounded VC dimension
11:40–12:30

Jay Tenenbaum (Tel Aviv University)

Locality-sensitive hashing for efficient similar polygon retrieval
12:30–14:00

Lunch (on your own)
14:00–14:30

Dror Aiger (Google)

From approximate incidences to camera posing and navigation
14:30–

Free time for discussion

Abstracts

Pankaj K. Agarwal (Duke University): Clustering under perturbation stability in near-linear time.

Abstract. We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is r-stable if the underlying optimal clustering continues to remain optimal even when all pairwise distances are arbitrarily perturbed by a factor of at most r. Our main contribution is in presenting efficient exact algorithms for r-stable instances whose running times depend near-linearly on the size of the data set for all clustering objectives when r > 2 + √3. For k-center and k-means problems, our algorithms  also achieve polynomial dependence on the number of clusters, k, when r > 2 + √3 + ε, in any fixed dimension. For k-medians, our algorithms have polynomial dependence on k for r > 5 in any fixed dimension; and r > 2 + √3 in two dimensions.

Joint work with Hsien-Chih Chang, Kamesh Munagala, Erin Taylo, and Emo Welzl.

Dror Aiger (Google): From approximate incidences to camera posing and navigation.

Abstract. I will give an overview on general techniques to compute approximate incidences [ESA’17, SOCG’19], their  application to the classical camera pose estimation problem that arises in many computer vision applications and their use in navigation application.

[link]

Joint work with Haim Kaplan and Micha Sharir.

[Slides]

Boris Aronov (New York University): Bipartite diameter and other measures under translation.

Abstract. In this talk I will impersonate Omrit Filtser by presenting her STACS talk. The abstract of the STACS paper was:

Let A and B be two sets of points in R^d, where |A| = |B| = n, so that the distance between them is defined by some bipartite measure dist(A, B). We study several problems in which the goal is to translate the set B, so that dist(A, B) is minimized. The main measures that we consider are

  1. the diameter in two and three dimensions, that is diam(A, B) = max{d(a, b) | a ∈ A, b ∈ B}, where d(a, b) is the Euclidean distance between a and b,
  2. the uniformity in the plane, that is uni(A, B) = diam(A, B) - d(A, B), where d(A, B) = min{d(a, b) | a ∈ A, b ∈ B}, and
  3.  the union width in two and three dimensions, that is uniwidth(A, B) = width(A ∪ B).

For each of these measures we present efficient algorithms for finding a translation of B that minimizes the distance: For diameter we present near-linear-time algorithms in R^2 and R^3 , for uniformity we describe a roughly O(n^{9/4})-time algorithm, and for union width we offer a near-linear-time algorithm in R2 and a quadratic-time one in R^3 .

This is joint work with Boris Aronov, Matthew J. Katz, and Khadijeh Sheikhan.

[Slides]

Paz Carmi (Ben Gurion University): Stabbing pairwise intersecting disks with four points.

Abstract. Following the seminal works of Danzer (1956, 1986) and Stachó (1965, 1981), and the recent result of Har-Peled et al. (2018), we study the problem of stabbing pairwise intersecting disks by points.

We prove that any set of pairwise intersecting disks in the plane can be stabbed by four points.

Our proof is constructive and yields a linear-time algorithm for finding the points.

Aruni Choudhary (Freie Universität Berlin): No-dimensional Tverberg theorems and algorithms.

Abstract. Tverberg’s theorem is a classic result in discrete geometry. It states that any finite d-dimensional point set of sufficiently large cardinality can be partitioned into k-subsets whose convex hulls have a common intersection. The computational problem of finding such a partition lies in the complexity class PPAD ∩ PLS. Recently, Adiprasito, Bárány, and Mustafa [SODA 2019] proved a no-dimensional version, in which the convex hulls of the sets in the partition may intersect in an approximate fashion. This relaxes the requirement on the size of the point set. The argument is constructive, but does not result in a polynomial-time algorithm. We present an alternative proof for a no-dimensional Tverberg theorem that leads to an efficient algorithm to find the partition. We give similar results for the colorful version of Tverberg theorem and a generalization of the Centerpoint and Ham-Sandwich theorems. To obtain our result, we generalize Sarkaria’s tensor product construction that reduces the Tverberg problem to the Colorful Carathéodory problem.

[Notes]

Esther Ezra (Bar Ilan University): Testing polynomials for vanishing on Cartesian products.

Abstract. Given three sets A, B, and C of real numbers, the 3SUM problem is to decide whether there is a triple a ∈ A, b ∈ B, c ∈ C that sums to zero. In this talk I will present a natural extension of this problem 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 problem is referred to as "3POL". This, in particular, includes the problem of collinearity testing in the plane, i.e., deciding whether there is a collinear triple of points–a fundamental problem in computational geometry with no known subquadratic solution.

In this talk I will first discuss the 3SUM problem and its recent developments, including a sketch of the algorithm of Gronlund and Pettie in the linear decision tree model. Then I will discuss the extension to 3POL in the algebraic decision tree model. I will first present the case where A, B, C are one-dimensional sets, which was addressed by Barba et al. (2017), and then present the scenario where these sets are two-dimensional. A main tool in our analysis is the so-called polynomial partitioning technique. As a main consequence of our analysis we obtain strict subquadratic bounds (in the algebraic decision tree model) for (i) collinearity testing, where one of the sets A, B, C is two dimensional (and the other two are one dimensional), and (ii) testing for triangle similarity, where all three sets are two dimensional.

Joint work with Boris Aronov and Micha Sharir.

[Slides]

Laszlo Kozma (Freie Universität Berlin): The complexity of permutation pattern matching.

Abstract. Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science. A natural algorithmic question is whether a given permutation of length n contains a given pattern of length k.

We give two new algorithms for this well-studied problem, one whose running time is n^{k/4+o(k)}, and a polynomial-space algorithm whose running time is O(1.6181^n). These results improve the earlier best bounds of n^{0.47k+o(k)} and O(1.79^n) due to Ahal and Rabinovich (2000) and Bruner and Lackner (2012), respectively, and are the fastest algorithms for the problem when k ∈ Ω(log n). We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens of constraint-satisfaction. We also look at lower bounds and special cases.

joint work with Benjamin Aram Berendsohn and Daniel Marx.

[Slides]

Wolfgang Mulzer (Freie Universität Berlin): Algorithms for disk graphs and transmission graphs – Recent developments.

Abstract. I will talk about some recent algorithmic results for (undirected) intersection graphs of disks and and their directed cousins, transmission graphs. Problems of interest are (dynamic) connectivity, shortest path computation, finding the girth, and distributed routing. This is an active area with plenty of challenging open problems, some of which will be mentioned in the talk.

[Slides]

Liam Roditty (Bar Ilan University): An almost 2-approximation for all-pairs of shortest paths in subquadratic time.

Abstract. In this talk I will present an algorithm that, given an unweighted undirected graph G, computes in O(m log n + n^{2−cε}) time, a data structure of size O(n^11/6). A query to the data structure is answered in constant time. For every u and v, the query returns an estimation d′ (u, v) such that: d(u, v) ≤ d′(u, v) ≤ (2 + ε)d(u, v) + 5, where d(u, v) is the distance between u and v in G.

This is the first result in which both the approximation factor is less than 3 and the running time is truly subquadratic.

Shakhar Smorodinsky (Ben Gurion University): An optimal extension of epsilon-nets for hypergraphs with bounded VC dimension.

Abstract. We study the following generalization of the notion of epsilon-nets in hypergraphs. Let H = (V, E) be a hypergraph 0 < eps < 1 a real and t > 1 an integer. We call a family N of subsets (of V) of cardinality t an eps-t-net if every hyperedge S in E with size at least eps|V| contains at least one set from N. When t = 1 this is the classical notion of epsilon-nets. We show that for any constant integers t, d any hypergraph with VC-dimension d admits an eps-t-net of size O((d/eps) log(1/eps)). Joint work with Noga Alon, Bruno Jartoux, Chaya Keller and Yelena Yuditsky.

Uri Stemmer (Ben Gurion University): How to find a point in the convex hull.

Abstract. This task may not be as easy as you think. Please come and see, you will get a lot of open problems to think about...

Tom Tsabar (Tel Aviv University): Optimized synthesis of snapping fixtures.

Abstract. Given a polyhedral workpiece P, which we need to hold, a snapping fixture is a semi-rigid polyhedron G, such that when P and G are well separated, we can push P toward G, slightly bending G on the way, and obtain a configuration, where G is back in its original shape and P and G are inseparable as rigid bodies. We prove a tight bound on the number of "fingers"' that such fixtures should have. We also present an algorithm for the automatic synthesis of such fixtures, which optimizes certain properties of them to make them more useful in practice. We describe two applications where our fixtures are used, with different optimization criteria: Fixtures to hold addons for drones, where we aim to make the fixture as lightweight as possible, and small-scale fixtures to hold precious stones in jewelry, where we aim to maximize the exposure of the stones, namely minimize the obscuring of the workpiece by the fixture.

This is joint work with Efi Fogel and Dan Halperin.

[Slides]

Jay Tenenbaum (Tel Aviv University): Locality-sensitive hashing for efficient similar polygon retrieval.

Abstract. Locality Sensitive Hashing (LSH) is an effective method of indexing a set of items to support efficient nearest neighbors queries in high-dimensional spaces. The basic idea of LSH is that similar items should produce hash collisions with higher probability than dissimilar items.

We study LSH for (not necessarily convex) polygons, and use it to give efficient data structures for similar shape retrieval. Arkin et al. represent polygons by their "turning function", a function which follows the angle between the polygon's tangent and the x-axis while traversing the perimeter of the polygon. They define the distance between polygons to be variations of the Lp (for p = 1,2) distance between their turning functions. This metric is invariant under translation, rotation and scaling (and the selection of the initial point on the perimeter) and therefore models well the intuitive notion of shape resemblance.

We develop and analyze LSH near neighbor data structures for several variations of the Lp distance for functions (for p = 1,2). By applying our schemes to the turning functions of a collection of polygons we obtain efficient near neighbor LSH-based structures for polygons. To tune our structures to turning functions of polygons, we prove some new properties of these turning functions that may be of independent interest.

As part of our analysis, we address the following problem which is of independent interest. Find the vertical translation of a function f that is closest in L1 distance to a function g. We prove tight bounds on the approximation guarantee obtained by the translation which is equal to the difference between the averages of g and f.

Emo Welzl (ETH Zürich): Bistellar and Edge Flip Graphs of Triangulations in the Plane: Geometry and Connectivity.

Abstract. The set of all triangulations of a finite point set in the plane attains structure via flips: The graph, where two triangulations are adjacent if one can be obtained from the other by an elementary flip. This is an edge flip for full triangulations, or a bistellar flip for partial triangulations (where non-extreme points can be skipped).

It is well-known (Lawson, 1972) that both, the edge flip graph and the bistellar flip graph are connected. For n the number of points and general position assumed, we show that the edge flip graph is (n/2 - 2)-connected and the bistellar flip graph is (n - 3)-connected. Both bounds are tight.

This matches the situation for regular triangulations (a subset of the partial triangulations), where (n - 3)-connectivity was known through the secondary polytope (Gelfand, Kapranov, Zelevinsky, 1990) and Balinski’s Theorem. We show that the edge flip graph can be covered by 1-skeletons of polytopes of dimension at least n/2 - 2 (products of associahedra). Similarly, the bistellar flip graph can be covered by 1-skeletons of polytopes of dimension at least n - 3 (products of secondary polytopes).

(covers joint research with Uli Wagner, IST Austria)

[Slides]

Meirav Zehavi (Ben Gurion University): Decompositions in UDGs and algorithmic applications in parameterized complexity.

Abstract. In this talk, we will focus on decompositions of geometric intersection graphs. In particular, we will see tree decompositions with special properties for unit disk graphs and map graphs. With respect to applications, we will employ these tree decompositions to design sub- and single-exponential time parameterized algorithms.

[Slides]

Contact Information