ComPoSe: Combinatorics on Point Sets and Arrangements of Objects

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.

In the context of industrial applications, the complex problems cannot be solved satisfactorily by using methods from a single branch of applied geometry. Instead, a combination of different approaches will often be needed. Therefore, the different fields of Applied Geometry, such as

* Computational Geometry,
* Computer Aided Geometric Design,
* Image Processing,
* Computer Vision,
* Kinematics and Robotics,

have started to become increasingly interconnected and begun even to merge.The proposed research in this FSP aims at creating an Austrian research community in this new and emerging field of Industrial Geometry.

Many questions in computational and combinatorial geometry are based on finite sets of points in the Euclidean plane. Several problems from graph theory also fit into this framework, when edges are restricted to be straight.
A typical question is the prominent problem of the rectilinear crossing number (related to transport problems and optimization of print layouts for instance): What is the least number of crossings a straight-edge drawing of the complete graph on top of a set of n points in the plane obtains?