Monday, May 14, 2007
Freie Universität Berlin
Institut für Informatik
Takustr. 9, 14195 Berlin
room 005
Lecture - 14:15
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
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.