08:5509:00 
Opening:
Emo Welzl 
09:0009:25 
Geometric Weight Balancing
Yoshio Okamoto, UEC Tokyo
(Gremo Apr 1, 2002  Mar 31, 2005)
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 threedimensional 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:2509:50 
On Totally Positive Matrices and Incidence Geometry
Shakhar Smorodinsky, Ben Gurion University
(Gremo Feb 15, 2004  Oct 31, 2004)
Abstract:
An mbyn 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 nbyn
TP matrix is Theta(n^{4/3}).
We study the problem of bounding the number of equal 2by2
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:5010: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)
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.

10:1510:40 
How to Pirate a Movie
Dominik Alban Scheder, Aarhus University
(Gremo Oct 17, 2005  July 31, 2011)
Abstract:
Some players participate in a peertopeer 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
lawenforcement 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:4011:10 
Coffee Break 
11:1011:35 
Kinetic 2Centers in the BlackBox Model
Bettina Speckmann, TU Eindhoven
(Gremo Oct 1, 2001  May 31, 2003)
Abstract:
We study two versions of the 2center problem for moving points in
the plane. Given a set P of n points, the Euclidean 2center
problem asks for two congruent disks of minimum size that together
cover P; the rectilinear 2center problem correspondingly asks
for two congruent axisaligned squares of minimum size that
together cover P. Our methods work in the blackbox 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 2center in amortized
sublinear time per time step, under certain assumptions on the
distribution of the point set P. For the Euclidean 2center we
give a similar result: we can maintain in amortized sublinear
time (again under certain assumptions on the distribution) a
(1+ε)approximation of the optimal 2center. 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:3512:00 
Efficient cplanarity Testing Algebraically
Radoslav Fulek, EPF Lausanne
Abstract:
We generalize the strong HananiTutte 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 cplanarity 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:0012:25 
Random Clique Game
Miloš Stojaković, University of Novi Sad
(Gremo May 15, 2002  Sept 30, 2005)
Abstract:
We will look at the MakerBreaker kclique 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
kclique; 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:2512:50 
Upper bounds for the Perimeter of Plane Convex Bodies
Filip Morić, EPF Lausanne
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.

12:5013:15 
Distinct Distances on two Lines
József Solymosi, University of British Columbia
(Gremo Jan 1, 2000  Mar 31, 2001)
Abstract:
Let P_{1} and P_{2} be two sets of points in the
plane, so that P_{1} is contained in a line L_{1},
P_{2} is contained in a line L_{2}, and
L_{1} and L_{2} are neither parallel nor
orthogonal. Then the number of distinct distances determined by the
pairs of P_{1} x P_{2} is
Ω(min{P_{1}^{2/3}P_{2}^{2/3},
P_{1}^{2}, P_{2}^{2}}). In
particular, if P_{1}=P_{2}=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.

13:1513:20 
Organizational Remarks:
Michael Hoffmann 