Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

Program — Combinatorial Algorithms Day 2013

6th Combinatorial Algorithms Day

Monday, June 24th 2013

All talks are in CAB G51 (the usual Mittagsseminar room).
Here is a PDF-map of ETH Zentrum.

08:55-09:00 Opening: Emo Welzl
09:00-09:25 Geometric Weight Balancing
Yoshio Okamoto, UEC Tokyo
(Gremo Apr 1, 2002 - Mar 31, 2005)

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.

09:25-09:50 On Totally Positive Matrices and Incidence Geometry
Shakhar Smorodinsky, Ben Gurion University
(Gremo Feb 15, 2004 - Oct 31, 2004)

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(n4/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.

09:50-10:15 On the Total Perimeter of Homothetic Convex Bodies in a Convex Container
Csaba Dávid Tóth, University of Calgary
(Gremo Mar 1, 2000 - Aug 31, 2002)

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.

10:15-10:40 How to Pirate a Movie
Dominik Alban Scheder, Aarhus University
(Gremo Oct 17, 2005 - July 31, 2011)

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.

10:40-11:10 Coffee Break
11:10-11:35 Kinetic 2-Centers in the Black-Box Model
Bettina Speckmann, TU Eindhoven
(Gremo Oct 1, 2001 - May 31, 2003)

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.

11:35-12:00 Efficient c-planarity Testing Algebraically
Radoslav Fulek, EPF Lausanne

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.

12:00-12:25 Random Clique Game
Miloš Stojaković, University of Novi Sad
(Gremo May 15, 2002 - Sept 30, 2005)

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.

12:25-12:50 Upper bounds for the Perimeter of Plane Convex Bodies
Filip Morić, EPF Lausanne

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.

12:50-13:15 Distinct Distances on two Lines
József Solymosi, University of British Columbia
(Gremo Jan 1, 2000 - Mar 31, 2001)

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

13:15-13:20 Organizational Remarks: Michael Hoffmann

Valid HTML 4.01!