Euclidean space | EPFL Graph Search

Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any positive integer dimension n, which are called Euclidean n-spaces when one wants to specify their dimension. For n equal to one or two, they are commonly called respectively Euclidean lines and Euclidean planes. The qualifier "Euclidean" is used to distinguish Euclidean spaces from other spaces that were later considered in physics and modern mathematics. Ancient Greek geometers introduced Euclidean space for modeling the physical space. Their work was collected by the ancient Greek mathematician Euclid in his Elements, with the great innovation of proving all properties of the space as theorems, by starting from a few fundamental properties, called postulates, which either were considered as evident (for example, there is exactly one

Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case

Valentin Hartmann

We consider the problem of finding an optimal transport plan between an absolutely continuous measure and a finitely supported measure of the same total mass when the transport cost is the unsquared Euclidean distance. We may think of this problem as closest distance allocation of some resource continuously distributed over Euclidean space to a finite number of processing sites with capacity constraints. This article gives a detailed discussion of the problem, including a comparison with the much better studied case of squared Euclidean cost. We present an algorithm for computing the optimal transport plan, which is similar to the approach for the squared Euclidean cost by Aurenhammer et al. (Algorithmica 20(1):61-76, 1998) and Merigot (Comput Graph Forum 30(5):1583-1592, 2011). We show the necessary results to make the approach work for the Euclidean cost, evaluate its performance on a set of test cases, and give a number of applications. The later include goodness-of-fit partitions, a novel visual tool for assessing whether a finite sample is consistent with a posited probability density.

SPRINGER HEIDELBERG2020

Regularity in metric spaces

Serguei Timochine

Using arguments developed by De Giorgi in the 1950's, it is possible to prove the regularity of the solutions to a vast class of variational problems in the Euclidean space. The main goal of the present thesis is to extend these results to the more abstract context of metric spaces with a measure. In particular, working in the axiomatic framework of Gol'dshtein – Troyanov, we establish both the interior and the boundary regularity of quasi-minimizers of the p-Dirichlet energy. Our proof works for quite general domains, assuming some natural hypotheses on the (axiomatic) D-structure. Furthermore, we prove analogous results for extremal functions lying in the class of Sobolev functions in the sense of Hajłasz – Koskela, i.e. functions characterized by the single condition that a Poincaré inequality be satisfied. Our strategy to prove these regularity results is first to show that, in a very general setting, the (Hölder) continuity of a function is a consequence of three specific technical hypotheses. This part of the argument is the essence of the De Giorgi method. Then, we verify that for a function u which is a quasi-minimizer in an axiomatic Sobolev space or an extremal Sobolev function in the sense of Hajłasz – Koskela, these technical hypotheses are indeed satisfied and u is thus (Hölder) continuous. In addition to that, we establish the Harnack's inequality for these extremal functions, and we show that the Dirichlet semi-norm of a piecewise-extremal function is equivalent to the sum of the Dirichlet semi-norms of its components.

EPFL2006

Reduced representations of complexes, signals, and multifiltrations

Celia Camille Hacker

The field of computational topology has developed many powerful tools to describe the shape of data, offering an alternative point of view from classical statistics. This results in a variety of complex structures that are not always directly amenable for machine learning tasks. We develop theory and algorithms to produce computable representations of simplicial or cell complexes, potentially equipped with additional information such as signals and multifiltrations. The common goal of the topics discussed in this thesis is to find reduced representations of these often high dimensional and complex structures to better visualize, transform or formulate theoretical results about them. We extend the well known graph learning algorithm node2vec to simplicial complexes, a higher dimensional analogue of graphs. To this end we propose a way to define random walks on simplicial complexes, which we then use to design an extension of node2vec called k-simplex2vec, producing a representation of the simplices in a Euclidean space. Furthermore, the study of this method leads to interesting questions about robustness of graph and simplicial learning methods. In the case of graphs, we study node2vec embeddings arising from different parameter sets, analysing their quality and stability using various measures. In the topic of signal processing, we explore how discrete Morse theory can be used for compression and reconstruction of cell complexes equipped with signals. In particular we study the effect of the compression of a complex on the Hodge decomposition of its signals. We study how the signal changes through compression and reconstruction by introducing a topological reconstruction error, showing in particular that part of the Hodge decomposition is preserved. Moreover, we prove that any deformation retract over R can be expressed as a Morse deformation retract in a well-chosen basis, thus extending the reconstruction results to any deformation retract. In addition, we introduce an algorithm to minimize the loss induced by the reconstruction of a compressed signal. Finally, we use discrete Morse theory to compute an invariant of multi-parameter persistent homology, the rank invariant. We can restrict a multi-parameter persistence module to a one- dimensional persistence module along any line of positive slope and compute the one-dimensional analogue of the rank invariant, namely the barcode. Through a discrete Morse matching we can determine critical values in the multifiltration, which in turn allows us to identify equivalence classes of lines in the parameter space. In our main result, we explain how to compute the barcode along any given line of an equivalence class given the barcode along a representative line. This provides a way to fiber the rank invariant according to the critical values of a discrete Morse matching and to perform computations in the corresponding one-dimensional module, which is much better understood.

EPFL2022

Reduced representations of complexes, signals, and multifiltrations

Celia Camille Hacker

EPFL2022