# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, November 9, 2009

Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
MA 005

Lecture - 14:15

### Isolated line transversals

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

### Probabilistic Matching of $d$-dimensional Shapes under Euclidean Motions

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.

Letzte Aktualisierung: 03.11.2009