Computational Geometry

Oblivious sketching enables efficient algorithms for analysing data streams and distributed data by reducing the number of data points while preserving a $(1+\epsilon )$-approximation for various regression loss functions such as $l_p$-norms, or logistic loss. For dense models, a sketching complexity of $\mathrm{\Omega }(d)$ is immediate. For very high-dimensional data, model sparsity is a common assumption, where we do not regress on all, but only on at most $k\ll d$ dimensions. While the computational complexity for solving this problem becomes hard, the assumption allows us to sketch to a smaller $o(d)$ size. We show that reducing to $\frac{k\log (d/k)}{{\epsilon }^2}$ is essentially optimal for any sketching algorithm under several regression losses, combining high-dimensional probability and geometry, information-theoretic arguments, and metric embedding theory.

In this talk, I present a parameterized algorithm for the planar disjoint paths problem. Given a planar graph $G=(V,E)$ and a set $T=\{(s_1,t_1),\mathrm{\dots },(s_k,t_k)\}$ of terminal pairs, the goal is to compute a set of vertex-disjoint paths, each connecting $s_i$ and $t_i$. This problem is NP-hard if we measure the running time as a function of the input size, but if we measure the running time as a function of $n$ and $k$, we can achieve a non-trivial bound. In this talk, I give a sketch of this algorithm with running time of $2^{𝒪(k^2)}n$. This improves the two previously best known algorithms running in $2^{𝒪(k^2)}{n}^6$ and $2^{2^{𝒪(k)}}n$ time, respectively.

In this talk, I prove an extension of the Borsuk–Ulam theorem for maps from $2$-sphere into $ℝ$. The extension says that there are always two antipodal points $S^2\ni x,-x$ such that $f(x)=f(-x)$ and the two points are connected in the preimage.

The proof uses the concept of the Reeb graph. We also consider the relationship between extra homology of the Reeb space of $f:S^n\to {ℝ}^{n-1}$ and the existence of the analogous extensions of the Borsuk–Ulam theorem.

Modern time series analysis requires the ability to handle datasets that are inherently high-dimensional; examples include applications in climatology, where measurements from numerous sensors must be taken into account, or inventory tracking of large shops, where the dimension is defined by the number of tracked items. The standard way to mitigate computational issues arising from the high dimensionality of the data is by applying some dimension reduction technique that preserves the structural properties of the ambient space. The dissimilarity between two time series is often measured by “discrete” notions of distance, e.g. the dynamic time warping or the discrete Fréchet distance. Since all these distance functions are computed directly on the points of a time series, they are sensitive to different sampling rates or gaps. The continuous Fréchet distance offers a popular alternative which aims to alleviate this by taking into account all points on the polygonal curve obtained by linearly interpolating between any two consecutive points in a sequence.

We study the ability of random projections à la Johnson and Lindenstrauss to preserve the continuous Fréchet distance of polygonal curves by effectively reducing the dimension.

In this talk, we discuss how modern SAT solvers can be used to tackle mathematical problems. We discuss various problems to give the audience a better understanding, which might be tackled in this fashion, and which might not. Besides the naïve SAT formulation further ideas are sometimes required to tackle problems. Additional constraints such as statements which hold “without loss of generality” might need to be added so that solvers terminate in reasonable time.

Modular robots consist of a large number (say $n$) of small identical modules that can move along each other to change the overall shape of the robot. A well-established model for modular robots is called sliding squares. Here, each module is represented by a square in the 2D grid, which form an edge-connected configuration. Modules can perform two types of moves: slides and convex transitions.

The main question now is: given a source and target configuration, can we find a short move sequence to transform the source into the target? In this talk I show an algorithm named Gather&Compact that finds such a move sequence of length $𝒪(Pn)$ where $P$ is the circumference of the configurations’ bounding box. Furthermore, I show that it is NP-hard to find a move sequence of minimum length.

The efficiency of deep learning applications deteriorates significantly as the sizes of the training data and of the neural networks grow larger. In this talk we identify beyond-state-of-the-art open problems in the intersection of deep learning with computational geometry. Motivated by the recent application of dynamic data structures for geometric halfspace range searching in the acceleration of deep neural networks’ training and preprocessing complexity, we revisit efficient algorithms for constructing geometric multi-dimensional data structures and maintaining them dynamically.

I first give a short history of computational complexity of puzzles and games, including combinatorial reconfiguration ones. In this context, there are three open problems.

1. 1.

   The Rubik’s cube has a similar property to one of the $n^2-1$ puzzles. Then what is the counterpart of the sliding block puzzle?

   • $\mathrm{■}$

     Is there some PSPACE-complete problem in general?

   • $\mathrm{■}$

     What about rectangular faces?

2. 2.

   Reconfiguration of triangulations of a simple polygon also has a similar property. Then, again, can we have a counterpart of the sliding block puzzle that leads us to PSPACE-complete variant in general?

   • $\mathrm{■}$

     How about non-simple polygon with holes?

   • $\mathrm{■}$

     Can the diameter of the configuration space be super-poly? (Otherwise, it is in NP since we have a poly-length witness.)

3. 3.

   Computational complexity of slide-and-pack puzzles. By some observations, it seems to be PSPACE-complete in general. Do we have some tractable restrictions?

In this talk we discuss the reconfiguration of arrangements of simple curves in the plane or on the sphere via triangle flips (a.k.a. Reidemeister moves of Type 3). This operation refers to the act of moving one edge of a triangular cell formed by three pairwise crossing curves over the opposite crossing of the cell, via a local transformation. We study two types of arrangements, namely, arrangements of pseudocircles in the plane and simple drawings of graphs on the sphere.

An arrangement of pseudocircles is a finite collection of simple closed curves in the plane such that every pair of curves is either disjoint or intersects in two crossing points. We show that triangle flips induce a connected flip graph on intersecting arrangements, i.e. on arrangements where every pair of pseudocircles intersects. To obtain this result, we first show that every intersecting arrangement can be flipped into some cylindrical arrangement, i.e. an arrangement where a single point stabs the interior of every pseudocircle. Then we show that the cylindrical arrangement can be flipped to a canonical arrangement, which also shows the connectivity of cylindrical intersecting arrangements of pseudocircles under triangle flips. With a careful analysis we obtain that the diameter of both flip graphs is cubic in the number of pseudocircles. The construction of the two flipping sequences makes essential use of variants of the sweeping lemma for pseudocircle arrangements due to Snoeyink and Hershberger [1].

A simple drawing of a labelled graph is a drawing in which the vertices are distinct points and the edges are simple curves connecting their endpoints. Moreover, any two edges share at most one point, which is either a common endpoint or a crossing. The extended rotation system of such a drawing is the collection of the rotations of all vertices and crossings of the drawing. The rotation of a vertex or crossing is the cyclic order in which the edges emanate from it. Gioan’s Theorem states that for any two simple drawings of the complete graph $K_n$ with the same crossing edge pairs, one drawing can be transformed into the other by a sequence of triangle flips. We investigate to what extent Gioan-type theorems can be obtained for wider classes of graphs. A necessary (but in general not sufficient) condition for two drawings of a graph to be transformable into each other by a sequence of triangle flips is that they have the same ERS. We show that for the large class of complete multipartite graphs, this necessary condition is in fact also sufficient and give bounds on the diameter of the resulting flip graph. We further show that this result is essentially tight in the sense that there exist drawings of multipartite graphs plus one edge or minus two edges which cannot be transformed into each other via triangle flips.

Differential privacy has become the de facto standard for personal information privacy, and has been recently widely adopted in both governments and the industry. Roughly speaking, a differentially private algorithm should have indistinguishable output distributions on neighbouring instances, which differ by one individual’s data. Such a definition also applies to geometric data, where one input point set has one more point than the other. In this talk, I give an overview of existing differentially private algorithms for geometric data, including range counting, mean estimation, and convex hull. I also discuss geometric privacy, a variant of differential privacy that is more suitable for certain geometric problems.

Partial Vertex Cover asks whether we can cover at least $t$ edges by selecting $k$ vertices. In contrast to vertex cover, this problem is NP-hard in bipartite graphs [1]. How about planar bipartite graphs?

It seems that the paper by Caskurlu et al. [1] asks this as an open problem, although “bipartite” is missing in the problem statement.

This problem is inspired by the obstacle-deletion problem by Subhash Suri. If this problem is NP-hard, we could use this fact in the following way for the obstacle-deletion open problem. Since the graph is bipartite, we can find a path in the plane (not in the graph) that crosses every edge exactly once. Now we interpret every vertex as obstacles, and for every edge, we make the corresponding obstacles interlock where the path would like to pass. Now partial vertex cover corresponds to allowing to delete $k$ obstacles while trying to get rid of as many interlockings as possible.

For the obstacle-deletion problem we can give weights to vertices, we can also give weights to edges. Therefore, even weighted versions of partial vertex cover in planar bipartite graphs would be of interest.

During the seminar, the following question from the talk given by Anna Lubiw was investigated. Given a set $P$ of $n$ points in the plane and two non-crossing spanning trees $T_r$, $T_b$ on $P$, what is their flip distance $\mathrm{dist}(T_r,T_b)$ in terms of $n$ in the worst case?

The following bounds are known:

1. 1.

   lower bound of $3/2\cdot n-5$ [3];

2. 2.

   upper bound of $2n-4$ [1];

3. 3.

   upper bound of $2n-\mathrm{\Omega }(\sqrt{n})$ if $P$ is in convex position [2].

Can these bounds be improved? Are there interesting special cases with tighter bounds?

Suppose we are in polygonal domain in the plane with $n$ vertices in total. The obstacles (holes) do not have to be convex. Given two points $s$ and $t$, what is the Euclidean length of the shortest path between $s$ and $t$ that may ignore $k$ obstacles? In other words, if we are allowed to remove $k$ obstacles, what is the length of the shortest obstacle-free path between $s$ and $t$? Formulated differently, let $ℬ$ be the set of $m$ disjoint simple polygons that are the obstacles. Define $d_{{ℬ}^{\prime }}(s,t)$ as the shortest path distance from $s$ to $t$ with only ${ℬ}^{\prime }\subseteq ℬ$ present. For given $k$ and $s$ and $t$, we wish to find

It is known how to compute the solution in polynomial time for convex obstacles [2]. A similar problem with overlapping obstacles is known to be intractable even for very simple obstacle shapes [2]. The weighted problem, where each obstacle has a cost and we are given a budget, is NP-hard even for vertical line segments as obstacles [1]. We would like to find out if the problem presented here is hard.

Consider a common definition of an uncertain trajectory as a sequence of uncertain points, where each uncertain point is some compact connected region, most commonly a disk in ${ℝ}^2$ or an interval in $ℝ$. A true location must be inside the region, but we do not know where. In this setting, it is natural to generalise the polyline metrics to ask for the maximum and minimum possible values. In particular, we say a polyline realises an uncertain trajectory if it is formed by a sequence of precise points, taken in the correct order from the uncertainty regions. Then we can ask for the lower bound and the upper bound distance, that is, given two uncertain curves, we want to find the minimum and the maximum distance between them over all realisations. Within this framework, we can use different uncertainty models. We can also use different distance metrics, most commonly, the Hausdorff or the Fréchet distance (or their variants).

Some of these combinations have previously been studied [1, 2, 3]; all either have a relatively simple polynomial-time solution, or are NP-hard. We can ask the following questions.

1. 1.

   For the directed Fréchet distance, the lower bound problem is in P, and the upper bound problem is NP-hard. For the directed Hausdorff distance, the situation is essentially reversed. Similar dichotomies exist for the weak (discrete) Fréchet distance, where different settings turn out to be NP-hard compared to the Fréchet distance. Is there something in common among the NP-hard variants? Why are the lower and upper bound problems reversed for NP-hardness?

2. 2.

   Can we fill in the gaps by studying the remaining variations, both for the Hausdorff and the Fréchet distance, and conclude for each whether it is NP-hard or solvable in polynomial time?