| [home] - [up] |
Abstract: Pseudo-Triangulations are a relaxation of triangulations (triangular meshes) where arbitrary polygons with exactly three corners are admitted as faces. Pseudo-triangulations enjoy various applications, including the areas visibility, ray shooting, rigidity, collision detection, and guarding.
The talk presents new geometric and combinatorial properties of pseudo-triangulations. Main results are a 3D embedding of pseudo- triangulations and a novel edge flip operation. Several consequences are discussed: Reduction of flip distances, construction of constrained regular complexes (special case: convex hulls), polytope representation of pseudo-triangulations.
Joint work with Oswin Aichholzer, Peter Braß, and Hannes Krasser.
Colloquium - 16:00
Abstract: A reversal rho=rho(i,j) is applied to a permutation pi:=pi_1...pi_n by reversing the order of elements pi_i...pi_j, thus it transforms pi into pi*rho=pi_1...pi_{i-1}pi_j...pi_ipi_{j+1}...pi_n. Sorting by reversals (MIN-SBR) is the problem of computing the minimum number of reversals required to transform a permutation pi into the identity permutation (1,...,n). This combinatorial problem has been widely studied in the last years, because it models genome rearrangements in computational biology applications. Recently, Caprara established that MIN-SBR is NP-hard.
Biologically more relevant is the problem of sorting signed permutations by reversals. In the signed case, each element of pi is associated with a sign of + or -, every reversal of a fragment pi_i...pi_j changes both the order and the signs of the elements, and we want to compute the minimum number of reversals required to transform pi to the signed identity permutation (+1,...,+n). The signed MIN-SBR problem, which was also believed to be NP-hard, can be solved in polynomial time. At present, the most efficient algorithm is due to Kaplan, Shamir and Tarjan (1997). In this talk we present their quadratic time algorithm for signed MIN-SBR and point out recent developments in the study of approximation algorithms for MIN-SBR.