CONFERENCIANTES INVITADOS
 
 

  Prosenjit K. Bose, On Flips in Triangulations.

  Jesús A. de Loera, Cómo contar puntos reticulares en poliedros: teoría, aplicaciones y software.

  Alberto Márquez, Problemas de etiquetado y Geometría Computacional.

  Emo Welzl, Counting Plane Graphs on Point Sets in the Plane.




  Prosenjit K. Bose, School of Computer Science, Carleton University, Canada.

On Flips in Triangulations.

We review a selection of results concerning edge flips in triangulations, concentrating mainly on various aspects of the following problem: Given two different triangulations, how many edge flips are necessary and sufficient to transform one triangulation into another. We study the problem both from a combinatorial perspective (where only a combinatrial embedding of the triangulation is specified) and a geometric perspective (where the triangulation is embedded in the plane, vertices are points and edges are straight-line segments.). We highlight both the similarities and differences of the two settings.

  Jesús A. de Loera, Dept. of Mathematics, University of California at Davis, USA.

Cómo contar puntos reticulares en poliedros: teoría, aplicaciones y software

Hay gran variedad de problemas que involucran contar el número de puntos enteros (o, más generalmente, puntos de un reticulo) que quedan dentro de una cierta región del espacio. Las aplicaciones van desde la matemática pura (geometría algebraica, teoría de la representación, polinomios de Ehrhart en combinatoria) hasta la aplicada (criptografía, programación entera, tablas de contingencia estadística).

Quizá el caso más básico es aquél en que la región es un poliedro convexo. En los años 90, ideas nuevas de geometría algebraica debidas a M. Brion y A. Khovanskii entre otros condujeron a A. Barvinok a proponer las funciones generatrices racionales como la estructura de datos ideal para representar puntos reticulares. En 1993, construyó un elegante algoritmo para su cálculo, de tiempo polinómico cuando la dimensión del politopo es fija. Hoy, nuevos descubrimientos muestran que las ideas algebraicas y analíticas son muy efectivas en la práctica, y la experimentación computacional nos permite atacar nuevas preguntas abiertas sobre retículos y poliedros. Esta charla es un "survey" de esta interesante area.

  Alberto Márquez, Dpto. de Matemática Aplicada I, Universidad de Sevilla.

Problemas de etiquetado y Geometría Computacional

Un típico problema de etiquetado (o etiquetado de mapa) trata de asignar rectángulos, u otras formas geométricas (estas son las etiquetas), a puntos de tal forma que dichos rectángulos no se solapen. Aunque existen multitud de variantes de este problema y para resolverlos se han utilizados recursos y herramientas de la geometría computacional, no se ha estudiado suficientemente la otra dirección, esto es: ¿qué problemas de la geometría computacional se pueden resolver a partir de herramientas y recursos que surgen del etiquetado de mapas? Comenzar a dar respuesta a esta pregunta es el tema de esta charla.

  Emo Welzl, Department of Computer Science, ETH Zürich.

Counting Plane Graphs on Point Sets in the Plane

We study extremal problems for the number of certain crossing-free graphs (with straight line embedding) spanned by a set of n points in the plane. One prominent result known in this context is an upper bound of O(59^n) for the number of triangulations of an n-point set by Francisco Santos and Raimund Seidel.

We discuss upper and lower bounds for Hamiltonian cycles (simple polygonizations), partial and perfect matchings, and crossing-free partitions. (The latter are partitions of the point set so that the convex hulls of the parts are disjoint. This problem can be easily formulated in terms of crossing-free graphs).

This is joint work with Micha Sharir.