EU - Connect - Combinatorics of Networks and Computation

Networks are present in our lives in numerous different environments: to name just a few, networks can model social
relationships, they can model the Internet and links between web pages, they might model the spread of a virus infection
between people, and they might represent computer processors/sensors that have to exchange information.
This project aims to obtain new insights into the behaviour of networks, which are studied from a geometric and
computational perspective. Thereto, the project brings together researchers from different areas such as computational
geometry, discrete mathematics, graph drawing, and probability. Among of the topics of research are enumerative problems
on geometric networks, crossing numbers, random networks, imprecise models of data, restricted orientation geometry.
Combinatorial approaches are combined with algorithms. Algorithmic applications of networks are also studied in the context
of unmanned aerial vehicles (UAVs) and in the context of musical information retrieval (MIR).
The project contains the work packages: “Geometric networks”, "Stochastic Geometry and Networks", “Restricted orientation
geometry”, “Graph-based algorithms for UAVs and for MIR”, and “Dissemination and gender equality promotion”.
The project connects researchers from 14 universities located in Austria, Belgium, Canada, Chile, Czech Republic, Italy,
Mexico, and Spain, who will collaborate and share their different expertise in order to obtain new knowledge on the
combinatorics of networks and applications.

FWF - ComPoSe - EuroGIAG_Erdös-Szekeres type problems for colored point sets and compatible graphs

This CRP focuses on combinatorial properties of discrete sets of points and other simple geometric objects primarily in the plane. In general, geometric graphs are a central topic in discrete and computational geometry, and many important questions in mathematics and computer science can be formulated as problems on geometric graphs. In the current context, several families of geometric graphs, such as proximity and skeletal structures, constitute useful abstractions for the study of combinatorial properties of the point sets on which they are defined. For arrangements of other objects, such as lines or convex sets, their combinatorial properties are usually also described via an underlying graph structure.

The following four tasks are well-known hard problems in this area and will form the backbone of the current project. We will consider the intriguing class of Erdős-Szekeres type problems, variants of graph problems with colored vertices, counting and enumeration problems for specific classes of geometric graphs, and generalizations of order types as a versatile tool to investigate the combinatorics of point sets. All these problems are combinatorial problems on geometric graphs and are interrelated in the sense that approaches developed for one of them will also be useful for the others. Moreover, progress in one direction might provide a better understanding for related questions. Our main objective is to gain deeper insight into the structure of this type of problems and to contribute major steps towards their final solution.

This CRP tackles fundamental questions at the intersection of mathematics and theoretical computer science. It is well known that in this area some problems require only days to be solved, others may take decades or even more. Thus, the working schedule with respect to obtaining the desired theoretical results must follow the standard approach: Continuation of work in progress, evaluation of the results obtained by other authors and groups, and continuous identification of new directions for progress and exploration, hence always advancing the frontiers of knowledge. Since it is infeasible to impose a proper temporal order on the objectives and milestones to be attained - the conceptual implications are manifold, and many of the stated objectives are strongly interrelated - it will be the very progress of research and the obtained results that mark our progress in time. This is guaranteed by the competence of the team. The major 'visible' milestones will be the regular presentations of joint papers in the main conferences of the field, the corresponding submissions to journals, and a series of progress reports that will help in keeping a clear and consistent guidance and interaction with the other teams.

Several of the mentioned problems are long-standing open questions and known to be hard. Therefore we will consider several specific variants of them to determine how far state-of-the-art methods can be used and where new approaches have to be found. This will definitely improve our understanding of the structure of these problems, with the goal of making major contributions towards their solution or, in the ideal case, to finally settle them. Most of our approaches will be of theoretical nature. But we will also make intensive use of computers for enumeration and experiments, to get initial insights into the structure of problems, or to support or refute conjectures.

It is well known that the mentioned problems have resisted several previous attacks and therefore require the cooperation of researchers with strong and complementary expertise. We consider large-scale collaboration on these topics as one of the main ingredients for success. Thus we will not have individual projects running in parallel, but all participants will jointly work on the topics, in a massive collaborative effort. To guarantee a strong interaction between the members of the group we will maintain regular exchanges of senior researchers and students, regular joint research workshops (1-2 per year), and frequent visits.

FWF - Computational geometry - NFN Industrial Geometry

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

(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.

(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.

FWF - Sensornetzwerk Seminar - Computational Geometry Seminar with Applications to Sensor Networks

Geometric objects such as points, lines and polygons are the key elements of a big variety of interesting research problems in computer science. With the rise of modern technologies, more and more of these tasks are solved by computers, as opposed to the classic pen-and-paper approach.
Over the last thirty years, researchers around the world have developed different techniques and algorithms that take advantage of the structure provided by geometry to sIn this thesis we consider triangles in the colored Euclidean plane.
We call a triangle monochromatic if all its vertices have the same color.
First, we study how many colors are needed so that for every triangle we can color the Euclidean plane in such a way, that there does not exist a monochromatic rotated copy of the triangle or a monochromatic translated copy of the triangle.
Furthermore, we show that for every triangle every coloring of the Euclidean plane in finitely many colors contains a monochromatic triangle, which is similar to the given triangle.
Then we study the problem, for which triangles there exists a 6-coloring, such that the triangle is nonmonochromatic in this 6-coloring.
We also show, that for every triangle there exists a 2-coloring of the rational plane, such that the triangle is nonmonochromatic.
Finally we give a 5-coloring of a strip with height 1, such that there do not exist two points with distance 1, which have the same color.
olve these problems.
This area of research, in between mathematics and computer science, is known as discrete and computational geometry. In this joint seminar we plan to use tools from discrete aIn this thesis we consider triangles in the colored Euclidean plane.
We call a triangle monochromatic if all its vertices have the same color.
First, we study how many colors are needed so that for every triangle we can color the Euclidean plane in such a way, that there does not exist a monochromatic rotated copy of the triangle or a monochromatic translated copy of the triangle.
Furthermore, we show that for every triangle every coloring of the Euclidean plane in finitely many colors contains a monochromatic triangle, which is similar to the given triangle.
Then we study the problem, for which triangles there exists a 6-coloring, such that the triangle is nonmonochromatic in this 6-coloring.
We also show, that for every triangle there exists a 2-coloring of the rational plane, such that the triangle is nonmonochromatic.
Finally we give a 5-coloring of a strip with height 1, such that there do not exist two points with distance 1, which have the same color.
Computational geometry (such as order-type-like properties, see below) and apply them to problems that
come motivated from the field of sensor networks.

Konzepte der Rechnerischen Geometrie - Theorie und Anwendung

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.

Optimizing Geometric Graphs

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.