Monday, November 9, 2009
Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
MA 005
Lecture - 14:15
Abstract:
A \emph{line transversal} to a family of convex objects in
$\Reals^{d}$ is a line intersecting each member of the family. There
is a rich theory of geometric transversals. A line~$\ell$ is an isolated
transversal of a family if any perturbation of~$\ell$ will miss a member
of the family.
In my talk, I will review some results about line transversals in the
plane, and how little of these results can be generalized to three and
higher dimensions. I will then present some results about isolated line
transversals that \emph{do} generalize to higher dimensions.
In particular, we have:
- if a family of disjoint balls in R^d has an isolated line transversal
$\ell$, then some subset of 2d-1 balls already has $\ell$ as a line
transversal.
- the constant 2d-1 here is correct: there are minimal families of
$2d-1$ balls that pin a line. Our proof of this lower bound is
interesting in that we cannot directly exhibit such minimal families.
Instead, we show that no family~$\FAM$ of at most $2d-2$ balls can be a
\emph{stable pinning} of a line~$\ell$, that is, there is always a
perturbation of~$\FAM$ such that the perturbed family no longer
pins~$\ell$. On the other hand, we show that there exist families of
stable pinnings of size~$2d-1$, implying that some perturbation of such
a family must be minimal.
- convex polytopes in $\Reals^{3}$ have pinning number six, at least
under a mild assumption: if a family $\FAM$ of convex polytopes pins a
line~$\ell$ and $\ell$ touches each polytope in the interior of an
edge, then there is a subfamily $\SFAM \subset \FAM$ of at most six
polytopes that already pins~$\ell$. The bound six is tight, as there
are minimal pinning families of four, five, and six disjoint
polytopes, and we can in fact completely characterize all pinning
configurations of a line by disjoint polytopes.
Colloquium - 16:00
Abstract:
Given a class of shapes $S$, a transformation group $T$ that acts on $S$,
and a similarity measure $\delta:S \times S \to \mathbb{R}$, the matching
problem w.r.t. $S$, $T$ and $\delta$ is the following: For two shapes $A,B
\in S$, find a transformation $t^\ast$ that maximizes $\delta(t(A),B)$
over all transformations $t \in T$. This is a well-studied problem for
several choices of $S$, $T$ and $\delta$. In most cases, $S$ contains only
2- or perhaps 3-dimensional shapes.
We consider as shapes sets of $d$-dimensional simplices in $\mathbb{R}^d$
that have pairwise disjoint interior, and we allow Euclidean motions as
transformations. Euclidean motions, or isometries, can be decomposed into
a rotational, a reflectional and a translational part. Rigid motions
consist only of rotations and translations. The proposed algorithm can be
adjusted to matching under rigid motions, which is interesting for
applications in computational biology. A mirrored shape is not considered
similar to its unmirrored counterpart in most biological applications.
We measure the similarity of shapes by the volume of the intersection. We
propose an algorithm that computes for two shapes $A$ and $B$ a Euclidean
motion $t$ such that $\operatorname{vol}(t(A) \cap B)$ is close to maximal
with high probability. In the talk, the algorithm and part of the analysis
are explained. This is ongoing work that generalizes an algorithm for
matching plane shapes under rigid motions by Helmut Alt, Ludmila Scharf,
and the speaker.