Frontiers of Geometric Algorithms

Schedule

Titles and Abstracts

• Andreas Wiese

  Title: Approximation algorithms for packing problems

  Abstract: Packing problems arise in many settings, for example, when loading cargo into a truck or a shop, when assigning virtual servers to real servers, and in general, when limited resources play a role. Packing problems are typically computationally hard; therefore, we do not expect to find efficient algorithms that solve them optimally. Thus, we study approximation algorithms which are efficient algorithms that compute solutions that are provably close to the optimal solution. In this talk, we will discuss classical and recent results in approximation algorithms for multi-dimensional geometric packing problems.

• Mikkel Abrahamsen

  Title: Online Sorting and Translational Packing of Convex Polygons

  Abstract: We investigate various online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container before the next piece is revealed; the pieces must not be rotated, but only translated. The aim is to minimize the used space depending on the specific problem at hand, e.g., the strip length in strip packing, the number of bins in bin packing, etc.

  We draw interesting connections to the following online sorting problem OnlineSorting \([\gamma,n]\): We receive a stream of real numbers \(s_1,\ldots,s_n, s_i\in[0,1]\), one by one. Each real must be placed in an array~\(A\) with \(\gamma n\) initially empty cells without knowing the subsequent reals. The goal is to minimize the sum of differences of consecutive reals in \(A\). The offline optimum is to place the reals in sorted order so the cost is at most \(1\). We show that for any \(\Delta\)-competitive online algorithm of OnlineSorting \([\gamma,n]\), it holds that \(\gamma \Delta \in\Omega(\log n/\log \log n)\).

  We use this lower bound to prove the non-existence of competitive algorithms for various online translational packing problems of convex polygons, among them strip packing, bin packing and perimeter packing. This also implies that there exists no online algorithm that can pack all streams of pieces of diameter and total area at most \(\delta\) into the unit square. These results are in contrast to the case when the pieces are restricted to axis-parallel rectangles, for which competitive algorithms are known. Likewise, the offline versions of packing convex polygons have constant factor approximation algorithms.

  On the positive side, we present an algorithm with competitive ratio \(O(n^{\log_2 3-1}\log n)=O(n^{0.59})\) for online translational strip packing of convex polygons. In the case of OnlineSorting \([C,n]\) for any constant \(C>1\), we present an \(O(2^{O(\sqrt{\log n\log\log n})})\)-competitive algorithm.

• Mathieu Mari

  Title: Sketching and Uncertainty: Through the Geometric Lens

  Abstract: We consider the Online Piercing of Rectangles problem, where given a fixed underlying grid of n points in the plane, a sequence R of m axis-parallel rectangles arrives in an online fashion, and an online algorithm must maintain a hitting set at any time, which is a set P of points of the grid such that every rectangle that has arrived so far must contain at least one point from P. Each time a rectangle arrives, the algorithm can add as many points as necessary but cannot remove points added previously. This problem was initially considered by Alon, Awerbuch, and Azar (STOC '03) in its most general version, where rectangles are replaced by arbitrary hyperedges a fixed set of points. They present a O(log n log m)-competitive algorithm, and an almost tight lower-bound of Ω((log n log m)/(log log n + log log m)). Since then, several works have considered restrictions to geometric cases (squares, disks, etc) and provided optimal O(log n)-competitive algorithms. However, all cases where an optimal competitive algorithm is known so far correspond to fat objects, and an important open question is to provide a O(log n)-competitive algorithm for rectangles, which probably form the simplest class of non-fat objects. Toward this goal, we provide a O(log n)-competitive algorithm when the rectangles form a system of pseudo-disks (i.e., without crossings). This requires a specific approach to take advantage of the underlying planarity of pseudo-disks. We also provide a simple O(log n)-competitive algorithm for the crossing-only case, which may be a positive sign for the existence of a O(log n)-competitive algorithm for the general case of axis-parallel rectangles.

• Malin Rau

  Title: A Tight (\( 3/2 + \varepsilon \))-Approximation Algorithm For Demand Strip Packing

  Abstract: In the Demand Strip Packing problem (DSP), we are given a set of jobs, each specified by a processing time and a demand. The task is to schedule all jobs such that they are finished before some deadline \(D\) while minimizing the peak demand, i.e., the maximum total demand of tasks executed at any point in time. DSP is closely related to the Strip Packing problem (SP), in which we are given a set of axis-aligned rectangles that must be packed into a strip of fixed width while minimizing the maximum height. DSP and SP are known to be NP-hard to approximate to within a factor below \(\frac{3}{2}\).

  To achieve the essentially best possible approximation guarantee, we prove a structural result. Any instance admits a solution with peak demand at most \(\big(\frac32+\varepsilon\big)OPT\) satisfying one of two properties. Either (i) the solution leaves a gap for a job with demand \(OPT\) and processing time \(\mathcal O(\varepsilon D)\) or (ii) all jobs with demand greater than \(\frac{OPT}2\) appear sorted by demand in immediate succession. We then provide two efficient algorithms that find a solution with maximum demand at most \(\big(\frac32+\varepsilon\big)OPT\) in the respective case. A central observation that sets our approach apart from previous ones, is that the properties (i) and (ii) need not be efficiently decidable: We can simply run both algorithms and use whichever solution is the better one.

• Sujoy Bhore

  Title: Sketching and Uncertainty: Through the Geometric Lens

  Abstract: In various applications, such as machine learning, robotics, and social choice theory, the input data, often represented geometrically as points in a finite metric space, can be massive in size. Efficient processing and representation of such large datasets is crucial. Sketching is a fundamental technique used to compress a large dataset into a smaller dataset while approximately preserving key properties. Among the various sketching mechanisms, two of the most important and well-studied sketching structures are spanners and tree covers. In the first part of this talk, I will discuss recent advances in geometric sketching methods. Traditional algorithmic models assume complete knowledge of the input in advance; however, this assumption often fails in dynamic settings, where inputs evolve over time. In such cases, algorithms must not only compute efficiently at each stage but also maintain high-quality solutions as the input undergoes updates. In the second part of the talk, I will explore the dynamic aspects of geometric sketching and discuss strategies for adapting algorithms to handle these challenges effectively.

• Anne Driemel

  Title: Finding Complex Patterns in Trajectory Data via Geometric Set Cover

  Abstract: We consider clustering problems that are fundamental when dealing with trajectory and time series data. The Fréchet distance provides a natural way to measure similarity of curves under continuous reparametrizations. Applied to trajectories and time series, it has proven to be very versatile as it allows local non-linear deformations in time and space. Subtrajectory clustering is a variant of the trajectory clustering problem, where the start and endpoints of trajectory patterns within the collected trajectory data are not known in advance. We study this problem in the form of a set cover problem for a given polygonal curve: find the smallest number k of representative curves such that any point on the input curve is contained in a subcurve that has Fréchet distance at most a given r to a representative curve.

• Matya Katz

  Title: Shrink and Bifurcate

  Abstract: We present the shrink-and-bifurcate optimization technique and some of its applications. The technique is useful when we have an efficient decision procedure, for which we do not have an efficient parallel implementation to facilitate standard parametric search. As one of its applications, we mention the, so called, reverse shortest path (RSP) problem: Given a set \(P\) of points, two designated points \(s,t \in P\), and an integer parameter \(k \ge 1\), find the smallest distance \(r^*\), so that there exists a path between \(s\) and \(t\) (through points of \(P\)) consisting of at most \(k\) edges, each of which of length at most \(r^*\).

• Neeldhara Misra

  Title: Geometric Puzzles

  Abstract: We will explore some folding, cutting, and packing problems that start off as recreational puzzlers, but lead us to interesting algorithmic questions. Some examples include the fold-cut scenarios, origami-inspired foldology puzzles, and packing puzzles involving polyominoes and circles. The talk will be survey-style and hands-on, where we will be guided by intuition to the discovery of some recurring themes.

• Tamal Dey

  Title: Geometry Brings Persistence to Combinatorial Dynamical Systems

  Abstract: A combinatorial framework for dynamical systems provides an avenue for connecting classical dynamics with data-oriented algorithmic methods. Combinatorial vector fields introduced by Forman and their recent generalization to multivector fields have provided a starting point for building such a connection. This brings a geometric flavor to the study of dynamical systems by defining them on a complex, e.g. a simplicial complex. Coincidentally, simplicial filtrations play a pivotal role in the persistence theory that led to the field of topological data analysis. Some recent work have indicated that there is possibly a closer relationship between combinatorial dynamical systems and persistence, simplicial filtration being a common denominator. In this work, we strengthen this relationship by showing that Connection Matrix that summarizes the flow structure among invariant sets in a dynamical system can be computed by a modified exhaustive reduction of a boundary matrix which is also a well known technique for computing persistence.

• Esther Ezra

  Title: Recent Developments on Intersection Searching in 3-Space

  Abstract: In this talk I will present several recent developments in the study of intersection searching. In such problems, we are given a set of simply-shaped objects (e.g., lines, simplices, balls, cylinders in some low dimension) and the goal is to preprocess them to a data structure that supports "range-intersection" queries, that is, the query is a geometric range (e.g., point, line, circular arc, simplex in low dimension) and we would like to report all the objects in the input that it intersects, or report that there are no such objects.

  Intersection searching is strongly related to semi-algebraic range searching, as well as to nearest-neighbor searching. In this talk I will discuss this connection, and will then present two concrete problems: Efficiently answering line-intersection queries amid unit balls in 3-space, and finding, amid a set of lines in 3-space, the nearest neighbor to a query point.

• Sharath Raghvendra

  Title: Fast Scaling Algorithms for the Semi-Discrete Optimal Transport Problem

  Abstract: In the semi-discrete optimal transport problem, we wish to transport mass from a discrete distribution \(\mu\) with a support set B containing \(n\) points inside a d-dimensional unit hypercube to a continuous distribution \(\nu\) (whose support is the entire \(d\)-dimensional unit hypercube) in a cost minimal way. In this talk, I will present new algorithms that run in \(n^{O(d)}\log\frac{1}{\delta}\) time and compute a semi-discrete optimal transport plan whose cost is within an additive error of \(\delta\). Our algorithms are based on interesting geometric interpretation of the cost scaling graph algorithms for the semi-discrete OT problem.

• Maike Buchin

  Title: Distance Measures for Geometric Graphs

  Abstract: Geometric graphs occur in many contexts and applications. In these one is often interested in their similarity, for instance if the embedded graphs are different representations of the same road network. We introduce and compare different distance measures for geometric graphs. The measures that we introduce are based on the (weak) Fréchet distance, a well-known distance measure for curves and surfaces. Our distance measures for geometric graphs take both their combinatorial structure as well as their geometric embedding into account. We study the computational complexity of these measures. For this, we first present a general algorithmic approach. Then we show that although deciding these distances is NP-complete in general, our approach yields polynomial time algorithms in several cases, for instance if the graphs are trees, or for the weak graph distance if both graphs are geometrically embedded in a nice way. Finally, we discuss extensions and open problems.

• Dan Halperin

  Title: From snapping fixtures to multi-robot coordination: Geometry at the service of robotics

  Abstract: Robots sense, move and act in the physical world. It is therefore natural that understanding the geometry of the problem at hand is often key to devising an effective robotic solution. I will review several problems in robotics and automation in whose solution geometry plays a major role. These include designing optimized 3D printable fixtures, object rearrangement by robot arm manipulators, and efficient coordination of the motion of large teams of robots. As we shall see, exploiting geometric structure can, among other benefits, lead to reducing the dimensionality of the underlying search space and in turn to efficient solutions.

• Santosh Vempala

  Title: Sampling by Algorithmic Diffusion

  Abstract: We present a new random walk for uniformly sampling high-dimensional convex bodies and logconcave distributions. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in Rényi divergence (which implies TV, W2, KL, \chi-squared). The proof departs from known approaches for polytime algorithms for the problem --- we utilize a stochastic diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the stationary density. The talk will be self-contained and run in discrete time.

• Yusu Wang

  Title: Size (length) generalization of neural models via Algorithmic alignment

  Abstract: Size (or length) generalization is a key challenge in neural algorithmic reasoning. Specifically, when can a neural model with bounded complexity generalize to problem instances of arbitrary (unseen) size? This problem, known as size generalization, is a special case of out-of-distribution (OOD) generalization. In this talk, I will present three examples of achieving such size generalization by "aligning" the neural models with algorithmic structures. In particular, the first two (quick) examples will be on the simpler "expressivity" question, where the goal is to design neural models that are capable of size generalization to solve potentially hard problems at hand. The main part of the talk will focus on the third example which goes beyond "expressivity" and tackles a much more challenging question of certifying, provably, that a trained model generalizes to input of arbitrary sizes. More precisely, we consider the problem of predicting the output of K-step Bellman-Ford (BF) procedure for computing graph shortest path. It has been observed in the literature that a special family of graph neural networks (which we refer to as BF-GNN) has a natural alignment with the BF procedure. Surprisingly, we show that we can construct a set of only a constant number of small graphs, such that if the neural Bellman-Ford model (even when over-parameterized) has low loss over these graphs, then this model will probably generalize to arbitrary graphs with positive weights. To the best of our knowledge, this is the first provable (and practical) generalization certificate for neural approximation of complex tasks. This result also has interesting implications on training neural algorithmic modules.

• John Hershberger

  Title: Snap Rounding: A Cautionary Tale

  Abstract: This talk describes the author's experience using and modifying the technique of snap rounding to meet the needs of a circuit verification system. The interplay of theory and practice illuminates the subtle challenges of both.

• Pankaj Agarwal

  Title: Multi-robot optimal motion planning

  Abstract: With the advancement of robotics, we witness the growing deployment of teams of robots in logistics, wildlife monitoring, buildings and bridges inspection and more. Motion planning for many robots requires that, in addition to not colliding with obstacles, the robots should not collide with one another, which in turn necessitates studying the problem in high-dimensional configuration spaces. Furthermore, we wish to ensure a good quality of the motion, such as being short or having a small makespan. Already for two simple robots, such as unit squares or discs, translating in a planar polygonal environment, little is known when it comes to optimizing the robot motion. This talks gives an overview of the recent progress on multi-robot optimal motion planning and discusses a few open problems.

• Mark de Berg

  Title: Clique-Based Separators

  Abstract: The Planar Separator Theorem states that any planar graph \(G=(V,E)\) with \(n\) nodes has a separator \(S\subset V\) of size \(O(\sqrt{n})\), that is, a subset \(S\) such that removing \(S\) from \(V\) splits the graph into components of size at most \(2n/3\). The Planar Separator Theorem has proven useful in developing efficient algorithms for various problems on planar graphs. Unfortunately, intersection graphs of geometric objects typically do not admit a separator of small size. Indeed, even a unit-disk graph does not necessarily have a small separator, because it can have arbitrarily large cliques. However, many geometric intersection graphs (including disk graphs) do admit so-called clique-based separators: separators that consist of a small number of cliques, instead of a small number of nodes. In this talk I will survey recent work on constructing clique-based separators, and I will discuss some applications.

• Saket Saurabh

  Title: Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles

  Abstract: Suppose we are given a pair of points \(s, t\) and a set \(\mathcal{S}\) of n geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (multi-)graph G with vertex set \(\mathcal{S}\) and every edge labeled from \(\{0, 1\}\), such that a set \(\mathcal{S}_d ⊆ \mathcal{S}\) of obstacles separates \(s\) from \(t\) if and only if \(G[\mathcal{S}_d]\) contains a cycle whose sum of labels is odd. Using this structural characterization of separating sets of obstacles we obtain the following algorithmic results. In the Obstacle-removal problem the task is to find a curve in the plane connecting s to t intersecting at most q obstacles. We give a \(2.3146^q n^{O(1)}\) algorithm for Obstacle-removal, significantly improving upon the previously best known \(q^{O(q³)} n^{O(1)}\) algorithm of Eiben and Lokshtanov (SoCG'20). We also obtain an alternative proof of a constant factor approximation algorithm for Obstacle-removal, substantially simplifying the arguments of Kumar et al. (SODA'21). In the Generalized Points-separation problem input consists of the set \(\mathcal{S}\) of obstacles, a point set \(A\) of \(k\) points and p pairs \((s_1, t_1), … (s_p, t_p)\) of points from \(A\). The task is to find a minimum subset \(\mathcal{S}_r \subseteq \mathcal{S}\) such that for every \(i\), every curve from \(s_i\) to \(t_i\) intersects at least one obstacle in \(\mathcal{S}_r\). We obtain \(2^{O(p)} n^{O(k)}\)-time algorithm for Generalized Points-separation. This resolves an open problem of Cabello and Giannopoulos (SoCG'13), who asked about the existence of such an algorithm for the special case where \((s_1, t_1), … (s_p, t_p)\) contains all the pairs of points in A. Finally, we improve the running time of our algorithm to \(f(p,k) ⋅ n^{O(\sqrt{k})}\) when the obstacles are unit disks, where \(f(p,k) = 2^{O(p)} k^{O(k)}\), and show that, assuming the Exponential Time Hypothesis (ETH), the running time dependence on \(k\) of our algorithms is essentially optimal.

• Tobias Mömke

  Title: A Linear Time Gap-ETH-Tight Approximation Scheme for TSP in the Euclidean Plane

  Abstract: The Traveling Salesman Problem (TSP) in the two-dimensional Euclidean plane is among the oldest and most famous NP-hard optimization problems. In breakthrough works, Arora [J. ACM 1998] and Mitchell [SICOMP 1999] gave the first polynomial time approximation schemes. The running time of their approximation schemes was improved by Rao and Smith [STOC 1998] to \((1/\epsilon)^{O(1/\epsilon)} n \log n\). Bartal and Gottlieb [FOCS 2013] gave an approximation scheme of running time \(2^{(1/\epsilon)^{O(1)}} n\), which is optimal in n. Recently, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS 2021] gave a \(2^{O(1/\epsilon)} n \log n\) time approximation scheme, achieving the optimal running time in \(\epsilon\) under the Gap-ETH conjecture. In our work, we give a \(2^{O(1/\epsilon)}\) n time approximation scheme, achieving the optimal running time both in n and in \(\epsilon\) under the Gap-ETH conjecture.

• Akanksha Agrawal

  Title: Applications of a constrained CSP to Parameterized Geometric Problems

  Abstract: Constraint Satisfaction Problems (CSP) are among very fundamental and well-studied problems. We will look at a restricted version of this problem that we call Monotone 2-CSP. This version admits a polynomial time algorithm, and our focus will be its application in obtaining parameterized algorithms for geometric problems. We will illustrate its application using a variant of the Art Gallery problem, and I will briefly state its other such applications.

• Siu-Wing Cheng

  Title: Fréchet Distance in Subquadratic Time

  Abstract: Let m and n be the numbers of vertices of two polygonal curves in ℝ\(^d\) for any fixed d such that m≤n. Since it was known in 1995 how to compute the Fréchet distance of these two curves in \(O(mn\log(mn))\) time, it has been an open problem whether the running time can be reduced to \(o(n^2)\) when \(m=\Omega(n)\). In the mean time, several well-known quadratic time barriers in computational geometry have been overcome: 3SUM, some 3SUM-hard problems, and the computation of some distances between two polygonal curves, including the discrete Fréchet distance, the dynamic time warping distance, and the geometric edit distance. It is curious that the quadratic time barrier for Fréchet distance still stands. We present an algorithm to compute the Fréchet distance in \(O(mn(\log\log n)^{2+\mu}\log n/\log^{1+\mu} m)\) expected time for some constant \(\mu\in(0,1)\). It is the first algorithm that returns the Fréchet distance in \(o(mn)\) time when \(m=\Omega(n\varepsilon)\) for any fixed \(\varepsilon\in(0,1]\).

• Kevin Buchin

  Title: Geometric Spanners: Bounded Tree-Width and Oriented Constructions

  Abstract: This talk explores two recent advancements on geometric spanners, which are graphs that approximate distances in a given metric space within a bounded factor. Such spanners enable efficient algorithmic solutions in computational geometry, especially when they exhibit desirable properties such as planarity or bounded tree-width.

  In the first part of the talk, I discuss the construction of geometric spanners with bounded tree-width, focusing on a worst-case optimal trade-off between dilation and tree-width. In the second part, I present oriented spanners, a new type of geometric spanner. An oriented spanner is an oriented graph in which, for any pair of distinct points, the shortest oriented closed walk containing them is at most a given factor longer than the perimeter of the smallest triangle containing those points. I will present new algorithmic results for constructing sparse oriented spanners.

• Sandeep Sen

  Title: The quest for a perfect algorithm for planar convex hull

  Abstract: It has been more than 50 years since the folklore algorithm for planar convex hulls, called Graham scan was published in 1972, and ever since, one of the most basic algorithmic problem in computational geometry has drawn attention of researchers from different generations. This simply stated problem has led to many interesting paradigms in geometric algorithms analogous to the way the problem of sorting had provided the early spark to the area of algorithm design and analysis. In this talk, we will trace the journey of this evergreen problem that has always unveiled a new facet whenever it was probed using a new light.

• David Woodruff

  Title: Adversarial Streaming

  Abstract: The majority of streaming problems are defined and analyzed in a static setting, where the data stream is any worst-case sequence of insertions and deletions that is fixed in advance. However, many real-world applications require a more flexible model, where an adaptive adversary may select future stream elements after observing the previous outputs of the algorithm. Over the last few years, there has been increased interest in proving lower bounds for natural problems in the adaptive streaming model. In this work, we give the first known adaptive attack against linear sketches for the well-studied \(\ell_0\)-estimation problem over turnstile, integer streams. For any linear streaming algorithm \(\mathcal{A}\) that uses sketching matrix \(\mathbf{A}\in \mathbb{Z}^{r \times n}\) where \(n\) is the size of the universe, this attack makes \(\tilde{\mathcal{O}}(r^8)\) queries and succeeds with high constant probability in breaking the sketch. We also give an adaptive attack against linear sketches for the \(\ell_0\)-estimation problem over finite fields \(\mathbb{F}_p\), which requires a smaller number of \(\tilde{\mathcal{O}}(r^3)\) queries. Finally, we provide an adaptive attack over \(\mathbb{R}^n\) against linear sketches \(\mathbf{A} \in \mathbb{R}^{r \times n}\) for \(\ell_0\)-estimation, in the setting where \(\mathbf{A}\) has all nonzero subdeterminants at least \(\frac{1}{\textrm{poly}(r)}\). Our results provide an exponential improvement over the previous number of queries known to break an \(\ell_0\)-estimation sketch.

• Amit Kumar

  Title: FPT approximation algorithms for Constrained Clustering Problems

  Abstract: Constrained clustering problems generalize classical clustering formulations, e.g., k-median, k-means, by imposing additional constraints on the feasibility of a clustering. There has been significant recent progress in obtaining approximation algorithms for these problems, both in the metric and the Euclidean settings. In this talk, I shall outline FPT approximation algorithms based on random sampling techniques for constrained clustering and outlier versions of these problems. This is based on joint work with Anup Bhattacharya and Ragesh Jaiswal.

• Karthik C. S.

  Title: Inapproximability of k-means and k-median: A Unified Framework

  Abstract: The state-of-the-art hardness of approximation results for the k-means and k-median problems come from two different techniques: Cohen-Addad, Karthik, and Lee [SODA'21] showed a reduction from a coloring problem to these clustering problems on n points in poly(n) dimensional \(L_\infty\)-metric space, and Cohen-Addad, Karthik, and Lee [SODA'22] showed a reduction from the Johnson coverage problem (a generalization of the vertex cover problem) to the two clustering problems on n points in \(O(\log n)\) dimensional \(L_1\) and \(L_2\)-metric spaces. In this talk, we present a common framework that unifies these two techniques by introducing a new graph clustering problem called k-Min-Max-Matching, where the task is to partition the vertex set to k parts so as to minimize the sum of the size of the maximum matching in the subgraphs induced by each part. We show that this new problem encompasses both techniques in our framework and moreover simplifies the soundness analysis of all previous inapproximability results, also resolving a couple of open problems.

• Chris Schwiegelshohn

  Title: A Tight VC-Dimension Analysis of Clustering Coresets with Applications

  Abstract: The VC dimension is a complexity measure often used in bounding the sample complexity. It is one of the earliest techniques we have to bound coreset sizes for various problems including k-median clustering, but still to this day not completely understood. In this work we give a tight analysis for bounding k-median coreset sizes via the VC dimension, recovering several optimal coreset bounds while also obtaining improved bounds for various geometric problems including minor-free graph metrics and Fréchet metrics.