Simplexe | EPFL Graph Search

En mathématiques, et plus particulièrement en géométrie, un simplexe est une généralisation du triangle à une dimension quelconque. Définition En géométrie, un simplexe ou n-simplexe est l'analogue à n dimensions du triangle. Il doit son nom au fait que c'est l'objet géométrique clos le « plus simple » qui ait n dimensions. Par exemple sur une droite (1 dimension) l'objet le plus simple à 1 dimension est le segment, alors que dans le plan (2 dimensions) l'objet géométrique clos le plus simple à 2 dimensions est le triangle, et dans l'espace (3 dimensions) l'objet géométrique clos le plus simple à 3 dimensions est le tétraèdre (pyramide à base triangulaire). Plus exactement, un simplexe est l'enveloppe convexe d'un ensemble de (n+1) points utilisé pour former un repère affine dans un espace affine de dimension n, ce qui signifie que :

sur une droite le repère sera fait d'une origine et de 1 point (généralement un repère (O, I), définissant l'unité de l'axe), et [OI] es

Collapse-invariant properties of spaces equipped with signals or directions

Stefania Ebli

Collapsing cell complexes was first introduced in the 1930's as a way to deform a space into a topological-equivalent subspace with a sequence of elementary moves. Recently, discrete Morse theory techniques provided an efficient way to construct deformation retracts collapsing one space into the other while preserving global topological properties. This type of collapse, called a Morse matching, has been widely used to speed up computations in (persistent) homology by reducing the size of complexes. Unlike classical collapses, in this thesis we consider topological spaces equipped with signals or directions. The main goal is then to reduce the size of the spaces while preserving as much as possible of both the topological structure and the properties of the signals or the directions. In the first part of the thesis we explore collapsing in topological signal processing. In this context, each signal on the cells of a complex is processed using the combinatorial Laplacian and the resultant Hodge decomposition.In Article 2.1 we provide an approach to signal compression and reconstruction on chain complexes that leverages the tools of algebraic discrete Morse theory. We first prove that any deformation retract of real finite-dimensional based chain complex is equivalent to a Morse matching. We then study the interaction between the Hodge decomposition and signal compression and reconstruction. Specifically, we prove that parts of a signal's Hodge decomposition are preserved under compression and reconstruction for specific classes of discrete Morse deformation retracts of a given based chain complex. Finally, we provide an algorithm to compute Morse matchings with minimal reconstruction error.Complementary to our theoretic results in topological signal processing, we provide two applications in this field. Article 2.2 extends graph convolutional neural networks to simplicial complexes, while Article 2.3 presents a novel algorithm, inspired by the well-known spectral clustering algorithm, to embed simplices in a Euclidean space. The object of our studies in the second part of the thesis is topological spaces equipped with a sense of direction. In the directed setting, the topology of the space is characterized by directed paths between fixed initial and terminal points. Motivated by applications in concurrent programs, we focus on directed Euclidean cubical complexes and their spaces of directed paths.In Article 3.1 we define a notion of directed collapsibility for Euclidean cubical complexes using the notion of past links, a combinatorial local representations of cubical complexes. We show that this notion of collapsability preserves given properties of the directed path spaces. In particular, we give sufficient conditions for a directed Euclidean cubical complex to have a contractible or a connected space of directed paths from a fixed initial vertex.In Article 3.2 we extend these results, providing further conditions for directed collapses to preserve the contractability or conneectdness of spaces of directed paths. Furthermore, we provide simple combinatorial conditions for preserving the topology of past links. These conditions are the first step towards developing an algorithm that checks at each iteration if a collapse preserves certain properties of the directed space.

EPFL2022

Hitting Simplices with Points in $R^3$

Abdul Basit

The so-called first selection lemma states the following: given any set P of n points in a"e (d) , there exists a point in a"e (d) contained in at least c (d) n (d+1)-O(n (d) ) simplices spanned by P, where the constant c (d) depends on d. We present improved bounds on the first selection lemma in a"e(3). In particular, we prove that c (3)a parts per thousand yen0.00227, improving the previous best result of c (3)a parts per thousand yen0.00162 by Wagner (On k-sets and applications. Ph.D. thesis, ETH Zurich, 2003). This makes progress, for the three-dimensional case, on the open problems of Bukh et al. (Stabbing simplices by points and flats. Discrete Comput. Geom., 2010) (where it is proven that c (3)a parts per thousand currency sign1/4(4)a parts per thousand 0.00390) and Boros and Furedi (The number of triangles covering the center of an n-set. Geom. Dedic. 17(1):69-77, 1984) (where the two-dimensional case was settled).

2010

Collapse-invariant properties of spaces equipped with signals or directions

Stefania Ebli

EPFL2022