21-25 August 2012
Portorož, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

THE ORDER TYPE DATA BASE

Presented by Prof. Oswin AICHHOLZER
Type: Keynote Lecture

Content

\begin{abstract} \noindent Many Problems in Computational Geometry and geometric Graph Theory are based on the most simple geometric objects: points in the plane and straight line segments connecting them. Moreover, for most combinatorial questions in this area only the ``discrete'' properties of the underlying point set have to be considered. More precisely, the crossing properties of the complete straight line graph spanned by the point set completely determine all combinatorial characteristics. These intersection properties can be coded by the {\it order type} of a point set $\{p_1,...,p_n\}$, established by Goodman and Pollack in 1983~\cite{GP}. The order type is defined as a mapping that assigns to each ordered triple $i,j,k$ in $\{ 1,...,n\}$ the orientation (clockwise or counterclockwise) of the triple $(p_i,p_j,p_k)$. Two point sets have the same order type if there is a bijection $\pi$ between these two sets such that for every triple $p_i,p_j,p_k$ of the first set, the corresponding points $\pi(p_i),\pi(p_j),$ and $\pi(p_k)$ have the same orientation. This allows to reduce the ``infinite'' problem of considering ``all sets of points of size $n$'' to a finite, combinatorial problem, and thus, to make it accessible for computer investigations. \noindent In recent years a complete order type data base for sets of cardinality $n \leq 11$ has been established, which is available online~\cite{DB}. It has been shown that this data base is complete, that is, it contains all the realizable, nonequivalent order types for $n \leq 11$ points in general position (that is, no collinear triples). Moreover, each order type is presented as a realizing point set with small integer coordinates, such that computations can be performed efficiently and without numerical problems. \noindent With the help of this data base -- and partial extensions of it -- already a vast number of problems from Computational Geometry and Graph Theory has been successfully investigated. Questions include intersection properties (crossing numbers), triangulations, perfect matchings, spanning trees and -paths, Erd\H{o}s-Szekeres type questions like convex (empty) \mbox{$k$-gons} and generalizations of it, to just name a few. We will report on several of the obtained results as well as on the generation and extension of the data base. \noindent Finally we will also discuss alternative versions of the order type, like colored versions, a globally directed order type, a geodesic order type, and applications of them. \end{abstract} \begin{thebibliography}{} \bibitem{GP} J.E.Goodman, R.Pollack, {\em Multidimensional sorting.} SIAM J. Computing 12 (1983), 484-507. \bibitem{DB} O. Aichholzer, {\em Enumerating Order Types for Small Point Sets with Applications.} {\tt http://www.ist.tugraz.at/aichholzer/research/rp/triangulations/ordertypes/} \end{thebibliography}

Place

Location: Portorož, Slovenia
Address: University of Primorska, Faculty of Tourism Studies, Obala 11a, SI-6320 Portorož - Portorose, Slovenia
Room: VP1

Primary authors

More