Arrangements of geometric objects and drawings of graphs lie at the core of modern Discrete and Computational Geometry. They serve as a exible tool in applications in both mathematics and computer science, since many important problems that involve geometric information may be modeled as problems on arrangements or graphs. Therefore, the study of these structures and a better understanding of their properties impacts a wide variety of problem domains. This DACH project \Arrangements and Drawings" connects groups that have already cooperated successfully in the European collaborative research programme EuroGIGA. In this follow-up project, we plan to investigate the relationships between different types of drawings and arrangements, as well as their abstract representations and their algorithmic properties. We have composed a list of challenging problems from the following four focus areas: (A) Arrangements of lines and pseudolines, (B) Drawings of graphs, (C) Structure of intersection, and (D) Planar and near-planar structures. The goal of this project is to gain insights in order to broaden our understanding of these areas and to jointly attack some of their long-standing open questions. These questions are notoriously diffcult though important, so that even partial solutions are expected to have impact.
Fördergeber*innen
• Österreichischer Wissenschaftsfonds FWF, FWF
Externe Partner
• Freie Universität Berlin
• Technische Universität Berlin, Institut für Mathematik
• Eidgenössische Technische Hochschule Zürich, ETH
Beginn: 26.08.2018
Ende: 25.08.2021
The general topic of this project is the investigation of geometric graphs, i.e., graphs where the vertex set is a point set in the plane and the edges are straight line segments spanned by these points. Throughout we assume the points to be in general position, that is no three of them lie on a common line, and to be labeled. Geometric graphs are a versatile data structure, as they include triangulations, Euclidean spanning trees, spanning paths, polygonalizations, plane perfect matchings and so on. The investigation of geometric graphs belongs to the field of (combinatorial) mathematics, graph theory, as well as to discrete and computational geometry. The alliance of our two research groups will perfectly cover these fields. For example this will allow us to use an interesting combination of enumerative investigations (lead by the Austrian team) and theoretical research (coordinated by the Spanish group). Let us point out that this combination of theoretical knowledge and practical experience, which is perfectly provided by the combination of these two teams, will be essential for the success of this project. There are many classic as well as new tantalizing problems on geometric graphs, and the investigation of seemingly unrelated questions often leads to new relations and deeper structural insight. So the focus of this project is to investigate several classes of problems with the common goal of optimizing properties of geometric graphs.
Fördergeber*innen
• Österreichischer Austauschdienst GmbH - Agentur für Internationale Bildungs- und Wissenschaftskooperation, OeAD
Externe Partner
• Universidad de Alcalá, E.T.S.I. Informática
Beginn: 31.12.2007
Ende: 30.12.2009
Zentrales Thema dieser gemeinsamen Forschung ist die Untersuchung grundlegender Datenstrukturen aus dem Bereich der rechnerischen Geometrie (Computational Geometry), einem relativ jungen Teilgebiet der (theoretischen) Informatik. Dabei sollen sowohl theoretische Aspekte untersucht werden, als auch deren konkrete Umsetzung im Rahmen einer allgemein verwendbaren Programmbibliothek. Auf Seite der theoretischen Untersuchungen sollen sowohl klassische Datenstrukturen, wie Voronoi-Diagramme oder Triangulierungen, aber auch relativ neue Datenstrukturen, wie Pseudo-Triangulierungen oder Straight-Skeletons, untersucht werden. Genauere Einzelheiten werden in den nachfolgenden Abschnitten beschrieben. Gleichzeitig soll aber auch für alle untersuchten Strukturen deren tatsächliche Verwendbarkeit in der Praxis berücksichtigt werden. So ist es geplant, jeweils spezielle Aspekte dieser Strukturen in konkreten Implementationen umzusetzen. Um einen bestmöglichen Nutzen der erzielten Ergebnisse zu gewährleisten, sollen die Implementationen in einer standardisierten Bibliothek der gesamten CG-Community zur Verfügung gestellt werden. Dazu ist die Umsetzung in CGAL (Computational Geometry Algorithms Library, siehe { www.cgal.org}) geplant. Es handelt sich dabei um ein ursprünglich von der EU gefördertes Projekt, das insbesondere von unserem französichen Projektpartner an zentraler Stelle mitbetrieben wird.
Fördergeber*innen
• Österreichischer Austauschdienst GmbH - Agentur für Internationale Bildungs- und Wissenschaftskooperation, OeAD
Externe Partner
• National Institute for Research on Computer Science and Control, Unité de recherche INRIA Sophia-Antipolis
Beginn: 31.12.2006
Ende: 30.12.2008

### Industrial Geometry - An emerging research area

Industrial geometry is based on computational techniques which originated in various areas of applied geometry. To give a few examples, the methods of Computer Aided Geometric Design form the mathematical foundation of the powerful CAD technologies available today. Computer Vision provides methods for inspecting and analyzing images and videos. Image processing is used to reconstruct geometric features from digital image data, such as X-ray or computer tomography images. Computational Geometry provides efficient algorithms for solving fundamental geometrical problems. Robot kinematics deals with geometric problems which occur in connection with robot mechanical systems.

In recent years, these different areas of research have started to become increasingly interconnected, and begun even to merge. A driving force in this process is the increasing complexity of applications, where one field of research alone would be insufficient to achieve useful results. Novel technologies for acquisition and processing of data lead to new and increasingly challenging problems, whose solution requires the combination of techniques from different branches of applied geometry.

Besides Subproject S09201: Coordination and Service, Knowledge transfer and sustainability, TU Graz hosts the following subprojects

#### Subproject S09205 (Computational Geometry)

(Principal Investigator: Oswin Aichholzer) Computational Geometry is dedicated to the algorithmic study of elementary geometric questions. Traditionally it deals with basic geometric objects like points, lines, and planes. For real world applications, however, often reliable techniques for advanced geometric primitives like surfaces and location query structures are needed.

The role of this project is twofold. On one hand it will provide the theoretical background for advanced geometric algorithms and data structures for several other projects within this joint research project (JRP). These include geometric structures for fast information retrieval, the generation and manipulation of triangular meshes, the computation of suitable distance functions to multidimensional objects, and the representation of advanced geometric objects.

Another aim of this project is to develop novel techniques for the manipulation and optimization of geometric structures. Here the emphasis is on geometric graphs (triangulation-like and Voronoi diagram-like structures, spanning trees). Properties of these structures will be investigated, with the goal of designing more efficient geometric algorithms and data structures.

Existing geometric algorithms libraries (CGAL, LEDA) will be used to guarantee robustness of the developed algorithms.

#### Subproject S09209 (Computational Differential Geometry)

(Principal investigator: Johannes Wallner) Computational Differential Geometry means methods of both numerical and discrete mathematics with the purpose of investigating and modeling curves and surfaces. The main theme of this research project is the robust analysis of differential properties of surfaces, the creation of discrete and semi-discrete models of freeform surfaces, and the study of geometric properties of such models. It is only recently that the wealth of interesting geometry connected to applications in, say, architecture, has come to the attention of mathematicians, and presumably only a small part of it has been investigated. We are investigating topics of Discrete Differential Geometry: discrete curvatures based on parallel meshes, quad-based and hex-based discrete surfaces, Christoffel duality, and others. New lines of research of semi-discrete surfaces and inverse problems in connection with integral invariants.

Fördergeber*innen
• Österreichischer Wissenschaftsfonds FWF, FWF
Externe Partner
• Johannes Kepler Universität Linz, Institut für Angewandte Geometrie
• Leopold-Franzens-Universität Innsbruck, Fakultät für Mathematik, Informatik und Physik, Institut für Informatik
• Technische Universität Wien, Geometric Modeling and Industrial Geometry
Beginn: 31.03.2005
Ende: 30.12.2011