Lectures and Colloquia during the semester

Freie Universität Berlin - Institut für Informatik

Takustraße 9, 14195 Berlin

Room 005

*Abstract:*
Let *C* be a closed and bounded set in the plane and let
*S* be a set of *n* points in the plane.
We consider the problem of computing a translate
of *C* that contains the maximum number of points of *S*. We start
by giving two basic algorithms for this problem whose running times
are roughly quadratic in *n*. Then we show how random sampling can be
used to transform any deterministic
algorithm for this optimal-placement problem
into a Monte Carlo approximation algorithm.
For sets *C* that satisfy a certain fatness condition, we use a
simple bucketing technique to transform any algorithm for
the optimal-placement problem into an algorithm that solves the same
problem. The bucketing transformation can be
implemented in the algebraic computation-tree model, or in a more
powerful model using hashing. Applying the
random-sampling and bucketing transformations to the two basic
algorithms, we obtain a variety of results. For example, if *C*
is a convex polygon with *m* vertices, we can solve the
optimal-placement problem in the algebraic computation-tree model
in *O(n \log n + mn \log (m k*) + n k*)* time, where *k** is the
number of points in an optimal placement of *C*. Also, for any
constants *epsilon,c>0*, we can compute a placement of *C* that
contains at least *(1 - epsilon) k** points in
*O(m + n \log (mn))* time with error probability at most
*e^{-c \sqrt{k*}}*. Employing hashing techniques, we can
implement this algorithm so that its running time is bounded by
*O(m + n \log m)*.

(This is joint work with Torben Hagerup and Rahul Ray.)

**Colloquium - 16:00**

*Abstract:*
Is it always possible to convexify a simple planar polygon with a
continuous motion that rotates the fixed-length edges around the vertices,
stays in the plane and avoids self-intersections? If so, then one can move
continuously from any configuration of a simple fixed-edge-length polygon
(or planar robot arm) to any other and maintain simplicity throughout. A
positive answer to this long standing open question was given recently by
Connelly, Demaine and Rote.
In this talk I describe an extension of this result to an effective,
efficient and surprisingly simple combinatorial approach for planning the
motion. It is based on a novel class of embedded minimally rigid planar
graphs called pseudo triangulations, which possess rich combinatorial
properties and can be characterized in many equivalent ways. I will
discuss the rigidity-theoretical properties of pseudo triangulations and
several algorithms for constructing and using them in the convexifying
motion.

[top]