Lectures and Colloquia during the semester

**December 13, 2004**

Freie Universität Berlin - Institut für
Informatik

Takustraße 9

14195 Berlin

Room 005
- map -

**Lecture - 14:15**

### Günter Rote -Freie Universität Berlin

### Strictly convex drawing of a planar graph

*Abstract:*
Every three-connected planar graph with n vertices has a drawing on an
*O*(*n*^{7/3})x*O*(*n*^{7/3}) grid
in which all faces are strictly convex polygons.
In proving this result, I will review the different approaches for obtaining
a graph drawing with convex faces (not necessarily strictly convex)
on a grid of linear side length, going back to Schnyder and to de Fraysseix,
Pach, and Pollack,
respectively.

I will discuss the number-theoretic problem that is involved in perturbing a
convex polygon into a strictly convex polygon, and related questions
of realizing convex polygons and convex polytopes on small integer grids.

**Colloquium - 16:00**

### Esther Moet -Utrecht University

### Guarding Art Galleries by Guarding Witnesses

*Abstract:*
The so-called Art Gallery Problems form an important subcategory within
the Computational Geometry. In my talk, we look at the following
problem: "Given a polygon *P*, does it admit a witness set, i.e., a set of
points in *P* such that any (prospective) guard set that guards the
witnesses is guaranteed to guard the whole polygon?" The idea, of
course, is that in the case of a set of moving guards, or of a guard set
that permits the addition or removal of guards, it is easier to check
point-to-point (i.e., guard-to-witness) visibility, than to update the
complete visibility region of all guards. We show that not all polygons
admit a finite witness set and prove several other combinatorial
properties of finite witness sets. We give an algorithm to compute a
minimum size witness set for *P* in *O(n*^{2} log n) time, if such a set
exists, or to report the non-existence within the same time bounds. We
also outline an algorithm that use a witness set for *P* to test whether a
(prospective) guard set sees all points in *P*.

[home] -
[up] -
[top]