# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, May 14, 2007

Freie Universität Berlin
Institut für Informatik
Takustr. 9, 14195 Berlin
room 005

Lecture - 14:15

### Probabilistic Shape Matching

Abstract:
The lecture presents probabilistic techniques for comparing shapes modeled by sets of line segments or by sets of polygons in the plane. These techniques have been developed in our group within the framework of the EU-funded project Perceptually Relevant Retrieval of Figurative Images (PROFI) and are, in particular, applied to finding similarities between trademarks.
The most simple variant is the question whether two shapes can be matched closely to each other by translations. This problem is solved by taking a sample point from each shape and giving a "vote" to that translation which maps one point to the other. If this experiment is repeated many times, clusters in the point cloud resulting in the space of translations indicate good matches. This idea is generalized to more complex transformations like rigid motions, similarity maps, or affine transformations.
We investigate which distance measures between shapes are optimized by this method and give probabilistic analyses determining how many experiments are necessary to obtain the desired results with a prespecified probability and accurateness. Further heuristics and experiments will be presented, as well.
Joint work with Ludmila Scharf, Sven Scholz, and Daria Schymura.

Colloquium - 16:00

### Dilation-minimal edge deletion in polygonal cycles

Abstract:
Frequently one has to degrade a given (geometric) network as gently as possible. Consider for example the case where some connections in a traffic network have to be shut down (e.g., due to budget considerations). Which edges of the network should be removed so as to not decrease the quality of the new network too much? In this talk we consider a simple variant of this problem: the initial network is a closed polygonal curve $P'$ in the plane, and we have to remove a single edge from that curve. We measure the quality of the resulting polygonal curve $P$ by considering its \emph{dilation} (or stretch factor) $\delta_P$. We give an $O(n \log^3 n)$ randomized algorithm for detecting an edge $e$ of the polygonal cycle $P'$ on $n$ vertices whose removal results in a polygonal curve $P \setminus \{e\}$ of smallest possible dilation.

Letzte Aktualisierung: 07.05.2007