12th Combinatorial Algorithms Day

Session 1

Abstract:
We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs.
We present a fully dynamic kinetic data structure that maintains a set of n disjoint growing squares. Our data structure uses O(n (log n loglog n)²) space, supports queries in worst case O(log² n) time, and updates in O(log⁵ n) amortized time. This leads to an O(n α(n) log⁵ n) time algorithm to solve the agglomerative clustering problem, which significantly improves upon the current best O(n²) time algorithms.
From a practical point of view, our new algorithm does not perform better than the naive algorithms for n < 10⁶. We hence also present an alternative agglomerative clustering algorithm which works efficiently in practice. Our algorithm relies on the use of quadtrees to speed up spatial computations. Interestingly, even in non-pathological datasets, we can encounter large glyphs that intersect many quadtree cells and that are involved in many clustering events. We therefore devise a special strategy to handle such large glyphs. We test our algorithm on several synthetic and real-world datasets and show that it performs well in practice.
This is joint work with Thom Castermans, Frank Staals, and Kevin Verbeek.

Abstract:
A family of sets ℱ is said to satisfy the (p,q) property if among any p sets in ℱ, some q have a non-empty intersection. Hadwiger and Debrunner conjectured in 1957 that for any p ≥ q ≥ d+1 there exists a constant c = c_d(p,q), such that any family of compact convex sets in ℝ^d that satisfies the (p,q) property, can be pierced by at most c points. Note that c_d(d+1,d) = 1 by Helly's theorem. In a celebrated result from 1992, Alon and Kleitman proved the conjecture. However, obtaining sharp bounds on c_d(p,q), called the "Hadwiger-Debrunner numbers", is still a major open problem in discrete and computational geometry. The best known lower bound is c₂(p,q) = Ω(p/q log p/q). We obtain a significantly improved lower bound of the form c₂(p,q) = Ω(p^1+Ω(1/q)).
This is joint work with Chaya Keller.

Session 2

Abstract:
Given a planar straight-line graph G=(V,E) in ℝ², a circumscribing polygon of G is a simple polygon P whose vertex set is V, and every edge in E is either an edge or an internal diagonal of P. A circumscribing polygon is a polygonization for G if every edge in E is an edge of P.
We prove that every arrangement of n disjoint line segments in the plane in general position (i.e., a geometric perfect matching) has a subset of size Ω(√n) that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to 3-space.
We show that it is NP-complete to decide whether a given graph G admits a circumscribing polygon, even if G is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to decide whether a geometric matching admits a polygonization.
This is joint work with Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, and Diane L. Souvaine.

Abstract:
In the Art Gallery Problem we are given a polygon P on n vertices and a number k. We want to find a guard set G of size k, such that each point in P is seen by a guard in G. Formally, a guard g sees a point p ∈ P if the line segment pg is fully contained inside the polygon P. The history and practical findings indicate that irrational coordinates are a "very rare" phenomenon. We give a theoretical explanation. Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical performance of algorithms, even if they perform badly in the worst case. The idea is to study the expected performance on small perturbations of the worst input. The performance is measured in terms of the magnitude of the perturbation and the input size. We consider four different models of perturbation. We show that the expected number of bits to describe optimal guard positions per guard is logarithmic in the input and the magnitude of the perturbation. This shows from a theoretical perspective that rational guards with small bit-complexity are typical. Note that describing the guard position is the bottleneck to show NP-membership. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an ER-complete problem was analyzed by Smoothed Analysis.
This is joint work with Michael Dobbins and Andreas Holmsen.
Here is a short (7 min.) video.

Abstract:
Motivated by communication scenarios such as timing channels and bit-shift channels, we study the error control problem in cases where the dominant type of noise are symbol shifts. In particular, we look at several channel models, determining their zero-error capacities by explicit constructions of optimal zero-error codes. In our first model, the information is stored in an n-cell register, where each cell is either empty or contains a particle of one of P possible types. Due to the imperfections of the device every particle is shifted k cells away from its original position over time, where k is drawn from a certain range of integers, without the possibility of reordering particles. Several variations of the above model are also discussed, e.g., with multiple particles per cell, with additional types of noise, and the continuous-time case.
This is joint work with Mladen Kovačević and Vincent Tan.