||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.
||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.
||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
Joint work with Adrian Dumitrescu.
||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
The goal of the players is to broadcast the movie from one player
to all players, without giving away the player who is broadcasting
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
|| Coffee Break
||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.
||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
||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
Joint work with Tobias Müller.
||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
Joint work with Alexey Glazyrin.
||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
|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.
|| Organizational Remarks: