Traditionally, the focus of computational geometry has been on tractable problems and a typical goal is to obtain subquadratic or even almost linear algorithms. Nevertheless, in the last fifteen years, a sizable subset of the computational geometry community has been actively dealing with NP-hard problems.
Two ways to cope with hardness in the realm of exact algorithms are fixed-parameter tractability and subexponential algorithms. The core techniques include small separators, shifting arguments à la Baker, treewidth-based algorithms, etc. On the complexity side, lower bounds based on the Exponential Time Hypothesis and hardness beyond NP such as ETR-hardness, the continuous counterpart of the (discrete) NP-hardness, have raised many intriguing and challenging open questions.
We consider the 3SUM and k-SUM problems, defined as fixed-parameter versions of the Subset Sum Problem: Given a set of n numbers, does there exist a subset of k of them whose sum is 0? The 3SUM problem was first considered by computational geometers as a way to argue of quadratic lower bounds for some natural geometric problems. It has since become a cornerstone of the so-called fine-grained complexity theory, dealing with the computational complexity of problems in P. We will review the notion of 3SUM-hardness and the relation between k-SUM and other problems. Then we will consider recent attempts to beat the quadratic barrier for 3SUM-hard problems. Finally, we will consider the design of efficient linear decision trees for k-SUM. All these ideas heavily rely on geometric notions.
Consider the following two problems on an edge-weighted planar graph G: given an integer k and a positive real r, is it possible (a) to pack k disjoint balls of radius r in G, and (b) to cover the whole vertex set of G using k balls of radius r? We view these problems through the lens of parameterized complexity: we consider the parameter k to be small and take it into account when measuring the running time of the algorithms. It appears that on one hand, the brute-force search running in time n^{O(k)} can be improved to time n^{O(sqrt{k})}, and on the other hand this improved running time is essentially tight: no algorithm with running time f(k) * n^{o(k)} can be expected assuming the Exponential Time Hypothesis. During the talk we will present both the technique behind the algorithmic result, which is based on a recursive scheme that exploits good separability properties of the Voronoi diagram induced by the solution, and the reduction methodology used for the lower bounds.
The art gallery problem deals with determining the minimum number of guards (or cameras) that are sufficient to cover or see every point in the interior of an art gallery, assuming that the guards have 360° visibility and can see an unbounded distance. An art gallery can be viewed as a polygon P (with or without holes) having a total of n vertices, while certain points in P can be specified as guards. Any point z in P is said to be visible from a guard g if the line segment joining z and g does not intersect the exterior of P. A polygon P is said to be guarded by a set of chosen guards if every interior point of P is visible from some guard within the guard set. This problem was first posed by Victor Klee at a conference in 1973, and in course of time it has become one of the important problems in computational geometry with extensive applications to surveillance of buildings like airport terminals, railway stations etc.
Most of the standard variants of the art gallery problem have been known to be NP-hard (though not NP-complete) since a long time, and very recently, these problems were shown to be ETR-complete. In 1998, Eidenbenz, Stamm and Widmayer established that the art gallery problem is APX-hard. They also proved that, especially when dealing with input polygons containing holes, the approximation ratio of O(log n) obtained by Ghosh in 1986 is in fact tight. In 2015, Bhattacharya, Ghosh and Roy showed that the approximation ratio lower bound of Ω(log n) holds even for the subclass of polygons with holes that are weakly visible from an edge. However, for the case of simple polygons without holes, a PTAS has been proposed very recently by Katz for vertex guarding the subclass of simple polygons that are weakly visible from an edge.
Ghosh also conjectured in 1986 that a constant-factor approximation algorithm exists for the art gallery problem when only vertex or edge guards are used and the input is restricted to only simple polygons without holes. In 2015, Bhattacharya, Ghosh and Roy settled this conjecture for the special class of simple polygons (without holes) that are weakly visible from an edge by presenting a 6-approximation algorithm for this problem. Recently, Bhattacharya, Ghosh and Pal designed constant factor approximation algorithms for guarding general simple polygons (without holes) using vertex guards.
In this talk, we present the hardness results for multiple variants of the art gallery problem, as mentioned above. We also outline a few approximation algorithms for solving some of these variants.
When proving lower bounds for geometric algorithms, one often faces the issue of placing "wires" (some kind of gadgets capable of carrying information over distance) in Euclidean space. These wires usually need to be disjoint in order to avoid conflicts. While some placement methods are known in two dimensions, the wire placement faces different obstacles in higher dimensions. Our Cube Wiring Theorem allows the placing of such wires in a compact manner in Euclidean space of dimension at least three; the placement can be used as a black box to get ETH-tight lowers bounds for several problems on geometric intersection graphs. The Cube Wiring Theorem can also be regarded as a theorem about graph minors: we show that all graphs are minors of a d-dimensional grid hypercube of a certain size. We end with a related wiring theorem for Hamming cubes, which has also been used for lower bounds recently.
Monday, June 11