Opendata, web and dolomites

Report

Teaser, summary, work performed and final results

Periodic Reporting for period 1 - ALPHA (Alpha Shape Theory Extended)

Teaser

The overall objective is the extension of the alpha shape theory beyond the original context of Delaunay mosaics as well as the integration of topological concepts that have developed in parallel over the last two decades. Extensions include to high dimensions, to...

Summary

The overall objective is the extension of the alpha shape theory beyond the original context of Delaunay mosaics as well as the integration of topological concepts that have developed in parallel over the last two decades. Extensions include to high dimensions, to dissimilarity measures other than the Euclidean distance, to k-fold rather than simple covers, and to abstract settings inspired by the geometric results.
The original alpha shape theory has had a substantial impact in the field, facilitating the reconstruction of 3-dimensional shapes from sampled data and opening up a whose research direction for modeling from data. The impact on society is sweeping as tools for 3D data enter fields of everyday life, such as geographic information systems, the analysis and simulation of molecular data, etc.

Work performed

The work performed in this project in divided into four objectives, each targeting a particular direction needed for the broad development of the theory. Objective I targets the possibility to adapt automatic reconstruction methods to local properties of the data, such as more detailed shaping where the data provides the necessary information, while keeping the global integrity of the reconstruction in other areas. A particularly successful approach is the Wrap algorithm, and: we have successfully generalized if to higher dimensions, non-Euclidean dissimilarities, k-fold covers, as well as the abstract context of monotonic functions on
polyhedral complexes.

Objective II addresses the stochastic properties of data and our algorithms. The former targets the understanding of noise while the purpose of the latter is to understand and possibly improve the behavior of the methods on the average. We had sweeping success in the study of Delaunay mosaics for Poisson point processes. This is the most fundamental geometric setting, and our topological approach to studying the geometry proved to be a fresh view on an old topic that allowed for major advances in our knowledge. In particular, we now have a complete understanding of the intervals and the critical stucture of a broad class of Delaunay mosaics up to dimension 4.

Objective III focuses on k-fold covers. Within the project, we were able to revive old subjects about order-k Voronoi diagrams, study new aspects, and extend their reach. For example, we now have an algorithm for computing persistence in depth, which means the characterization of the covering as the depth decreases. This kind of analysis is challenged by the absence of a consistent complex that represents the covers for different depths.

Objective IV extends the theory to periodic settings. Here we focus on the 3-dimensional case and questions that arise in the study of materials. We have made progress in the development of a stable invariant that can be used to search and organize periodic crystals.With the availability of millions of structures, this will be an important piece in the creation of new computational infra-structure supporting high-performance approaches to materials.

Final results

We have novel research results on all four objectives:
- the extension of the Wrap algorithm to abstract settings;
- expressions for the expected number of simplices in Delaunay mosaics;
- algorithm for persistent homology in depth;
- stable invariant for periodic crystal structures.

Website & more info

More info: http://alpha.pages.ist.ac.at/.