[home] - [up]


Lectures and Colloquia during the semester



Monday, May 9, 2005

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 042           - map -
Lecture - 14:15

Ingo Althöfer -Friedrich-Schiller-Universität Jena

Evaluation and Tuning of Combinatorial Board Games with Computer Help

Abstract: Inventing board games is a time-consuming process. Especially, the testing of prototypes takes a lot of time, with many rounds of improvement, modification, and retesting. Recently developed intelligent computer programs like "Zillions of Games" (by Mark Lefler and Jeff Mallett) and "Morphling" (by Thomas Rolle) may help to speed up the testing considerably.

The speaker used such computer help in the invention of several new games. In the talk two of these games are demonstrated: "SO oder SO oder SO oder SO" and "EinStein würfelt nicht".

In the report http://www.minet.uni-jena.de/preprints/althoefer_03/CAGI.pdf relevant background material may be found.


Colloquium - 16:00

Tzvetalin Vassilev -University of Saskatchewan

Optimal Area Triangulations

Abstract: We consider a set of n points in the two--dimensional Euclidean plane. A triangulation is a subdivision of the interior of the convex hull of the point set into triangles, created by a maximal set of non--intersecting straight line segments induced by the point set.

In the literature many criteria for optimality of a triangulation have been considered. In this talk, we focus on optimizing the area of the individual triangles in the triangulation. In particular, we are interested in MinMax area triangulation, which is the triangulation that minimizes the area of the largest area triangle in the triangulation over all possible triangulations of the given point set. Similarly, we consider the MaxMin area triangulation.

When the point set is in convex position, both optimal area triangulations can be computed in O(n2 log n) time and O(n2) space. The algorithms that achieve these bounds will be discussed in detail. These algorithms rely on number of geometric properties that are going to be discussed. The optimal triangulations have a particular structure which allows an efficient use of dynamic programming. Special data structures and algorithmic techniques are also employed. In addition, the decision version of the MaxMin problem is decidable in O(n2 log log n) time and quadratic space.

When the point set is in general position, the exact computation of the optimal area triangulations is of unknown complexity. We present an approach to approximation of the optimal triangulations. We achieve this by imposing angular constraints on the approximating triangulation. Further, we study perfect matchings between the approximating triangulation and the optimal one, and derive bounds for the approximating factors. The approximating triangulations are computed within (sub)cubic time and quadratic space.


[home] - [up] - [top]