Chromatic alpha complexes

Figure 1.  Mingling patterns distinguished by the number of colors forming a cycle and the number of additional colors filling this cycle. The drawings are caricatures of similar patterns for cycles different from circles and fillings different from disks. The patterns are but a first attempt to differentiate types of interactions, and they are by no means precise or exhaustive. For example, two additional colors can fill a cycle in at least two different ways (see the pattern of type 1+2): in a collaboration as suggested in the drawing, or each individually, like two different patterns of type 1+1

Figure 2.  On the left: a set, $ A \subseteq {{\mathbb R}}^2 $, together with its Voronoi tessellation, $ {{\rm Vor}_{({{A}})}} $, and one Voronoi ball highlighted. On the right: the union of disks, $ \bigcup_{a\in A} {{B}_{{r}}{({{a}})}} $, with the alpha complex, $ {{\rm Alf}_{{r}}{({{A}})}} $, superimposed

Figure 3.  Two empty stacks in $ {{\mathbb R}}^2 $ that pass through one blue point, two green points, and one orange point forming a simplex $ \nu\in{{\rm Del}_{({{\chi}})}} $. (In fact, the stack on the right passes through two orange points, and it also passes through the one orange point that the left orange circle passes through.) The set of centers of all empty stacks that pass through these four points is the intersection of three Voronoi cells: a blue 2-cell, a green 1-cell, and an orange 2-cell. The right panel shows the smallest empty stack in this collection: its center lies on the boundary of the intersection of Voronoi cells, which is the reason why one of its circles passes through an extra point

Figure 4.  An obtuse triangle with two blue points and an orange point at the obtuse angle. The smallest empty sphere that passes through the three points on the left has strictly larger radius than the smallest empty stack that passes through the three points on the right. Therefore, the triangle belongs to both, the Delaunay complex and the chromatic Delaunay complex, but it has a different value under the two radius functions

Figure 5.  On the left: a chromatic set together with the Voronoi tessellations of the blue and orange points overlaid, and one chromatic Voronoi ball highlighted. On the right: the union of blue and the union of orange disks

Figure 6.  The chromatic lifting for points in $ {{\mathbb R}}^2 $ with two colors. Left: the chromatic Delaunay complex embedded in three dimensions using the lifted points as vertices; it is isomorphic to the Delaunay complex of the lifted points. The triangles and tetrahedra with more than one color are left unfilled for clarity. Right: the union of disks of radius $ r $, for each color separately on the two sides, and for both colors together in the middle. As defined shortly in Section 3.4, each plank (solid cylinder) connects a disk in the middle with the same disk on one of the sides. We show one such cylinder for each color

Figure 7.  The chromatic lifting for points in $ {{\mathbb R}}^1 $ with three colors. Left: the chromatic Delaunay complex embedded in three dimensions using the lifted points as vertices; it is isomorphic to the Delaunay complex of the lifted points. The triangles and tetrahedra are left unfilled for clarity. Right: the union of segments of length $ 2r $, for each color separately along the three lines. Note the barycentric subdivision of the triangle at the bottom, and the parallel lines emanating from the midpoints of the edges and the barycenter of the triangle. As defined shortly, each plank is a quadrangular prism that connects one of the intervals with its projections to three of these parallel lines. We show one such prism for each color

Figure 8.  The union of bi-chromatic planks for a tri-chromatic point set in $ {{\mathbb R}}^1 $. It is homotopy equivalent to the bi-chromatic subcomplex of the corresponding chromatic alpha complex. On the left, we show the planks in the sides of the triangular prism erected on top of the barycentrically subdivided color triangle. On the right, the three sides of the triangular prism are unfolded into the plane, and the planks are glued along the orange dashed lines. A similar unfolding one dimension higher helps us to understand the situation for the 2-dimensional data in Figure 9

Figure 9.  The union of bi-chromatic planks for a tri-chromatic point set in $ {{\mathbb R}}^2 $. For clarity, only one plank per color is shown. Every blue, green; and yellow disk is connected to its gray counterparts via a solid cylinder. By construction, the planks are subsets of the boundary faces of a 4-dimensional triangular prism. Similar to Figure 8, we unfold the 3-dimensional boundary so we can illustrate the planks in $ {{\mathbb R}}^3 $, as shown. Observe the highlighted 2-hole in the middle: this is a topological feature that captures a loop created by one color (blue) and filled by each of the other two colors. This is one variant of the pattern of type 1+2 from Figure 1

Figure 10.  The columns in this matrix are the gradient vectors after combining them as explained in the proof of Lemma 4.5. Zero entries are left blank. There are $ s+1 $ blocks of columns, one for each color. The respective first columns of the first $ k+1 $ blocks contain $ \nabla h_0 $ and $ \nabla h_j - \nabla h_0 $, for $ 1 \leq j \leq k $. The points of colors 0 to $ k $ all lie on the same sphere, and we get vectors by subtracting the same point, $ c_0 $, from each such point. For each color $ j \geq k+1 $, we get vectors from the points in block $ j $ by subtracting an arbitrary but fixed point $ c_j \in B_j $

Figure 11.  An example showing that chromatic genericity is needed for the radius function to be generalized discrete Morse. Two blue points, $ a,b $, and two orange points, $ c,d $, share a common bisector and therefore violate the chromatic genericity condition in Definition 4.1. Indeed, the four points also lie on a common circle. The two shown circles belong to the smallest empty circumstack of the simplex $ abcd $. This stack is still the smallest empty circumstack for the edges $ ab $, $ ad $, and $ bc $, but not of any single vertex. Hence, the set of simplices that share the radius with $ abcd $ does not have a unique minimum and is therefore not an interval

Figure 12.  A bi-chromatic point set on the left, and a tri-chromatic point set on the right. The dotted line indicates the separation of green from orange points that form the background for the blue circle

Figure 13.  The 6-pack for the bi-chromatic point set in the left panel of Figure 12. The domain, $ L $, is the blue subcomplex of the codomain, $ K $, which is the 3-dimensional chromatic Delaunay complex of the blue and orange points

Figure 14.  Example showing that five diagrams do not imply the sixth. The two filtrations differ by a single 2-dimensional cell added in the respective fourth steps of the filtrations. Correspondingly, five of the 1-dimensional persistence diagrams (shown as barcodes) are the same, while the highlighted diagrams of the codomain differ on the two sides

Figure 15.  The four exact sequences for three complexes drawn along sine-like curves in the plane. After each half-period, the dimension of the homology group drops by one

Figure 16.  The 6-pack of $ (L,M) \subseteq (K,M) $ for the data in the right panel of Figure 12. $ M $, $ L $, and $ K $ are the 1-, 2- and 3-chromatic subcomplexes of the chromatic Delaunay complex