6th Combinatorial Algorithms Day

Abstract:
Given a simple polygon P, a point t in P, and a set of positive weights, we want to place the weights on the boundary of P in such a way that their barycenter comes to t. We show that there is always such a placement if the weights are balanced, i.e., no weight is larger than half of the total weight, and the placement can be found efficiently. We also study three-dimensional versions of the problem.
Joint work with Luis Barba, Jean Lou De Carufel, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yuan Tang, Takeshi Tokuyama, Sander Verdonschot, and Tianhao Wang.

Abstract:
An m-by-n matrix is called totally positive, TP, if all its square minors are positive. Totally positive matrices play an important role in many facets of mathematics. Farber et al. proved that the maximum possible number of equal entries in an n-by-n TP matrix is Theta(n^4/3).
We study the problem of bounding the number of equal 2-by-2 minors in TP matrices, and, in doing so, discuss various connections to incidence geometry. In the talk, we will describe these connections, as well as some open problems.
Joint work with Miriam Farber and Saurabh Ray.

Abstract:
For two convex bodies, C and D, consider a packing S of n positive homothets of C contained in D. We estimate the total perimeter of the bodies in S, denoted per(S), in terms of n. When all homothets of C touch the boundary of the container D, we show that either per(S)=O(log n) or per(S)=O(1), depending on how C and D "fit together", and these bounds are the best possible apart from the constant factors. Specifically, we establish an optimal bound per(S)=O(log n) unless D is a convex polygon and every side of D is parallel to a corresponding segment on the boundary of C (for short, D is parallel to C).
When D is parallel to C but the homothets of C may lie anywhere in D, we show that per(S)=O((1+esc(S)) log n/log log n), where esc(S) denotes the total distance of the bodies in S from the boundary of D. Apart from the constant factor, this bound is also the best possible.
Joint work with Adrian Dumitrescu.

Abstract:
Some players participate in a peer-to-peer protocol. One players knows a secret (a movie) which she wants to share with the other players. Sadly, all communication is eavesdropped by the copyright law-enforcement authority.
The goal of the players is to broadcast the movie from one player to all players, without giving away the player who is broadcasting it.
So the other players have to behave as if they also had the movie - although they don't - in order to confuse the copyright authority, but not too much, lest they completely obstruct the broadcasting of the movie.
We give some upper and lower bounds on the ability of the players to achieve their goal.
Joint work with Joshua Brody, Sune Jakobsen, and Peter Winkler.

Abstract:
We study two versions of the 2-center problem for moving points in the plane. Given a set P of n points, the Euclidean 2-center problem asks for two congruent disks of minimum size that together cover P; the rectilinear 2-center problem correspondingly asks for two congruent axis-aligned squares of minimum size that together cover P. Our methods work in the black-box KDS model, where we receive the locations of the points at regular time steps and we know an upper bound on the maximum displacement of any point within one time step. We show how to maintain the rectilinear 2-center in amortized sub-linear time per time step, under certain assumptions on the distribution of the point set P. For the Euclidean 2-center we give a similar result: we can maintain in amortized sub-linear time (again under certain assumptions on the distribution) a (1+ε)-approximation of the optimal 2-center. In many cases - namely when the distance between the centers of the disks is relatively large or relatively small - the solution we maintain is actually optimal. We also present results for the case where the maximum speed of the centers is bounded.
Joint work with Mark de Berg and Marcel Roeloffzen.

Abstract:
We generalize the strong Hanani-Tutte theorem to clustered graphs with two disjoint clusters, and show that an extension of our result to flat clustered graphs with three disjoint clusters is not possible. We also give a new and short proof for a result by Di Battista and Frati about efficient c-planarity testing of an embedded flat clustered graph with small faces. Our proof is based on the matroid intersection algorithm.
Joint work with Jan Kynčl, Igor Malinović, and Dömötör Pálvölgyi.

Abstract:
We will look at the Maker-Breaker k-clique game played on the edge set of the random graph G(n,p). In this game, two players, Maker and Breaker, alternately claim unclaimed edges of G(n,p) until all the edges are claimed. Maker wins if he claims all the edges of a k-clique; Breaker wins otherwise. We determine the probability threshold for the graph property that Maker wins this game. On top of that, we give a more precise result for k=3, describing the hitting time of Maker's win in the random graph process.
Joint work with Tobias Müller.

Abstract:
We show that the maximum total perimeter of k plane convex bodies with disjoint interiors lying inside a given convex body C is equal to per(C) + 2(k -1) diam(C), in the case when C is a square or an arbitrary triangle. A weaker bound is obtained for general plane convex bodies. As a consequence, we establish a bound on the perimeter of a polygon with at most k reflex angles lying inside a given plane convex body, answering our question posed at GWOP 2012.
Joint work with Alexey Glazyrin.

Abstract:
Let P₁ and P₂ be two sets of points in the plane, so that P₁ is contained in a line L₁, P₂ is contained in a line L₂, and L₁ and L₂ are neither parallel nor orthogonal. Then the number of distinct distances determined by the pairs of P₁ x P₂ is Ω(min{|P₁|^2/3|P₂|^2/3, |P₁|², |P₂|²}). In particular, if |P₁|=|P₂|=m, then the number of these distinct distances is Ω(m^4/3), improving upon the previous bound Ω(m^5/4) of Elekes.
Joint work with Micha Sharir and Adam Sheffer.