Lexicographic optimal chains and critical bases

David Cohen-Steiner, André Lieutier, Julien Vuillamy

► To cite this version:

David Cohen-Steiner, André Lieutier, Julien Vuillamy. Lexicographic optimal chains and critical bases. Journal of Applied and Computational Topology, 2026, 10 (1), pp.3. 10.1007/s41468-025-00230-y. hal-05498949

HAL Id: hal-05498949

https://hal.science/hal-05498949v1

Submitted on 7 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Lexicographic optimal chains and critical bases

David Cohen-Steiner<sup>1,2†</sup>, André Lieutier<sup>†</sup> and Julien Vuillamy<sup>3†</sup>

<sup>1</sup>Campus SophiaTech, Université Côte d'Azur, Biot, France.

<sup>2</sup>Datashape project, Inria Sophia Antipolis - Mediterranée, Valbonne, France.

<sup>3</sup>Dassault Systèmes Provence, Aix-en-Provence, France.

Contributing authors: david.cohen-steiner@inria.fr; andre.lieutier@gmail.com; julien.vuillamy@gmail.com; <sup>†</sup>These authors contributed equally to this work.

## Abstract

Previous works on lexicographic optimal chains have shown that they provide meaningful geometric homology representatives while being easier to compute than their $l^1$-norm optimal counterparts. We present a novel algorithm to efficiently compute lexicographic optimal chains with a given boundary in a triangulation of 3-space, by leveraging a Lefschetz duality at the chain level and an augmented version of the classical disjoint-set data structure. We also show that the space of lexicographic optimal cycles forms a vector space isomorphic to the homology groups of the complex, a property suggesting a parallel with $l^2$-norm optimal chains and Hodge theory. A canonical basis for this space of lexicographic optimal chains can be defined, called *critical basis*, and we show how to compute it using standard matrix reduction algorithms. In applications, we show how both computing optimal chains with a given boundary and critical bases offer new promising ways of efficiently reconstructing open surfaces in difficult acquisition scenarios.

**Keywords:** lexicographic optimality, optimal chains, simplicial homology, homology generator, Lefschetz duality, Delaunay triangulation, disjoint-set, critical basis, open surface reconstruction
# 1 Introduction

## 1.1 Localization problems

Computing meaningful homology generators has attracted significant interest due to its numerous applications related to shape analysis, computer graphics, computer-aided design, or topological data analysis.

The most studied setting for homology generators associates a weight to each $k$-simplex and minimizes the $l^1$-norm over chains, corresponding to the weighted sum of the simplex coefficients in the chain. In particular, we are often interested in the two following problems:

- computing the optimal $k$-chain homologous to a given chain;

- computing the optimal $k$-chain bounded by a given $(k-1)$-boundary.

Whether these problems are tractable depends mainly on the coefficients used. For instance, for integer modulo 2 coefficients ($\mathbb{Z}_2$), both problems are known to be NP-hard for $k > 1$ and even hard to approximate within any constant factor [1, 2]. For integer coefficients, finding optimal cycles in their homology classes can be shown to be tractable in favorable cases, for example when the boundary matrix can be shown to be unimodular, meaning that the solution of the linear relaxation problem has integer coefficients [3].

A few other positive complexity results can be found in particular settings [4–6]. Most notably, for a $d$-pseudomanifold, finding the optimal $(d-1)$-cycle in its homology class is equivalent to a minimum-cut problem on the dual graph of the complex [7–9].

## 1.2 Lexicographic optimality

Lexicographic optimality offers an alternative way of defining homology representatives, where the order between chains is induced by a total order on simplices. The advantages of this approach are two-fold. Firstly, both previously stated problems are polynomial-time tractable for any coefficient field. Algorithms solving these problems have strong connections with the matrix reduction algorithms used to compute persistent homology and have cubic complexity in the size of the simplicial complex [10]. Secondly, when the total order on simplices is well-chosen, lexicographic optimal chains give geometrically meaningful homology representatives. For instance, Delaunay triangulations, and more generally regular triangulations, can be characterized as lexicographic optimal chains in the full complex built on the vertex set [11].

The particular case of lexicographic optimal cycles in codimension 1 of a pseudomanifold can be computed more efficiently. Whereas the $l^1$-norm setting had a $O(n^2)$ time complexity [12], the lexicographic problem is equivalent to a *lexicographic* cut on the dual graph and can be solved in $O(n \log n)$ time complexity. Using the particular order on simplices of Definition 7 below, some applications have taken advantage of this appealing complexity for the efficient and accurate meshing of large point clouds, as shown on Figure 1: see [10] for more details.
<figure><img src="image_2.png" /><figcaption>**Fig. 1:** Illustration of lexicographic optimal chains in the context of closed surface reconstruction. The closeup shows that small features are correctly recovered. Taken from [10].</figcaption></figure>

However, no efficient algorithm was known to compute the lexicographic optimal chain with a given boundary in this favorable setting.

## 1.3 Contributions

After giving a formal definition of lexicographic orders on simplicial chains, Section 2 explores a few properties of lexicographic minimality. In particular, we show that the map that associates to a cycle its lexicographic optimal homologous cycle is linear and therefore that the space of lexicographic optimal cycles forms a vector space isomorphic to the homology groups of the complex. The next three sections are then dedicated to providing an efficient algorithmic solution to compute lexicographic optimal chains from given boundaries in the Delaunay triangulation. As described in Section 3, this requires to compute a representative non-optimal chain followed by finding the optimal chain homologous to this representative chain. After describing a Lefschetz duality at the chain level in Section 4, we give a $O(n \log n)$ algorithm for computing the optimal homologous relative ($d-1$)-chain in a $d$-pseudomanifold. These results are detailed in Section 5. Note that, aside from its use in this particular context,
we believe the described augmentation to the disjoint-set data structure is of independent interest and could be a useful tool in different applications.

In Section 6, we describe the first part of the algorithm, i.e. finding a (non-optimal) representative 2-chain bounded by given 1-boundary.

Section 7 is dedicated to defining a canonical basis for the space of lexicographic optimal cycles called *critical bases* and relates the computation of such a basis to standard matrix reduction algorithms.

Finally, in Section 8, algorithms developed in this work, both for computing optimal chains with a given boundary and for constructing critical bases are illustrated in the context of open surface reconstruction. Note that most of the algorithms in this work are presented using relative chains. This is mainly justified by applications: where the absolute setting will require to exactly define the input boundary of the reconstruction problem, the relative setting will allow the use of a detector to define the input boundaries more loosely in the form of a subcomplex, offering interesting possibilities for triangulating open surfaces or even stratified objects in difficult scenarios.

# 2 Lexicographic optimality on simplicial chains

## 2.1 Definitions

We expect the reader to be familiar with simplicial homology. We recall in Appendix A all notions required in the context of this work. In all that follows, $K$ will denote a simplicial complex of dimension $d$. The set of $k$-simplices of $K$ is denoted by $K^{(k)}$. For an arbitrary field $\mathbb{F}$, $C_k(K; \mathbb{F})$, or simply $C_k(K)$, denotes the vector space of absolute $k$-chains on $K$ over coefficients in $\mathbb{F}$. $Z_k(K)$ and $B_k(K)$ denote the vector space of $k$-cycles and $k$-boundaries of $K$. The support $|\Gamma|$ of a chain $\Gamma$ corresponds to the set of simplices with non-zero coefficients.

We assume a total order on $k$-simplices is given, which will be denoted by $\leq$. This order allows to derive the following total preorder on $k$-chains.

**Definition 1** (Lexicographic total preorder) Given $\Gamma_1, \Gamma_2 \in C_k(K)$,

$$ \Gamma_1 \subseteq_{lex} \Gamma_2 \iff_{\text{def.}} \begin{cases} |\Gamma_1| = |\Gamma_2| \\ \text{or} \\ \max \{\sigma \in |\Gamma_1| \Delta |\Gamma_2|\} \in |\Gamma_2| \end{cases} $$

where $\Delta$ denotes the set symmetric difference.

A corresponding strict order $\subseteq_{lex}$ can be defined:

$$ \Gamma_1 \subseteq_{lex} \Gamma_2 \iff_{\text{def.}} (\Gamma_1 \subseteq_{lex} \Gamma_2) \quad \text{and} \quad \neg(\Gamma_2 \subseteq_{lex} \Gamma_1) $$
**Observation 1** Consider $\Gamma_1, \Gamma_2 \in C_k(K; \mathbb{F})$.

$$ (\Gamma_1 \sqsubseteq_{lex} \Gamma_2 \quad \text{and} \quad \Gamma_2 \sqsubseteq_{lex} \Gamma_1) \iff |\Gamma_1| = |\Gamma_2| $$

When $\mathbb{F} = \mathbb{Z}_2$, the preorder $\sqsubseteq_{lex}$ is a total order.

All previous definitions extend naturally to relative chains for a simplicial pair $(K, B)$.

## 2.2 Properties of lexicographic optimality

We characterize the existence, uniqueness, and linearity of lexicographic optimal chains. These properties of lexicographic minima can be best understood in the abstract context of quotient vector spaces. Consider a pair $A \subset E$ of finite-dimensional vector spaces, with a given ordered basis of $E$:

$$ e_1 < \dots < e_n $$

inducing a lexicographic preorder $\sqsubseteq_{lex}$ on $E$.

**Lemma 1** Given $x \in E$, the minimum under the total preorder $\sqsubseteq_{lex}$ in the following application $M_{lex}^A$ exists and is unique:

$$ \begin{array}{l} M_{lex}^A : E \to E \\ x \mapsto \min_{\sqsubseteq_{lex}} x + A \end{array} \qquad (1) $$

*Proof* We call the support $|x| \subset \{e_1, \dots, e_n\}$ of $x \in E$ the set of basis elements for which the corresponding coordinates in $x$ are not zero. Since $x \in x + A$, the set $x + A$ is not empty. Since there is a finite number of supports on the space $x + A$, there exists a minimal support, and therefore at least one minimal vector. Assume, for a contradiction, that there exists $x_1, x_2 \in x + A$, $x_1 \neq x_2$, minimum under the preorder $\sqsubseteq_{lex}$. Consider a basis element $\sigma \in |x_2 - x_1|$. From Observation 1, we have that $|x_1| = |x_2|$, therefore $|x_2 - x_1| \subset |x_1|$ and $\sigma$ is in $|x_1|$. We now consider the following vector:

$$ x_3 = \underset{\text{def.}}{x_1} - \frac{x_1(\sigma)}{(x_2 - x_1)(\sigma)}(x_2 - x_1) $$

As $x_1 \in x + A$ and $x_2 - x_1 \in A$, we have that $x_3$ belongs to $x + A$. By construction, it is also smaller than $x_1$ for the preorder $\sqsubseteq_{lex}$, as $|x_3| \subset |x_1| \setminus \{\sigma\}$. This is a clear contradiction with the definition of $x_1$ as a minimum of $x + A$. $\square$

**Lemma 2** The application $M_{lex}^A$ is linear. In other words, for $x_1, x_2 \in E$ and $\lambda \in \mathbb{F}$,

$$ M_{lex}(x_1 + \lambda x_2) = M_{lex}(x_1) + \lambda M_{lex}(x_2) $$
Proof Recall that $\forall x \in E, M_{lex}^A(x) - x \in A$, so that one can define $a \in A$ as:

$$a = \underset{\text{def.}}{M_{lex}(x_1 + \lambda x_2) - M_{lex}(x_1) - \lambda M_{lex}(x_2)} \qquad (2)$$

Assume for a contradiction that $a \neq 0$ and take $\sigma_{\max} = \max|x|$. The basis element $\sigma_{\max}$ belongs to the support of (at least) one of the three terms of Eq. (2). We assume first that $\sigma_{\max} \in |M_{lex}(x_1)|$. We now have the following chain:

$$x = \underset{\text{def.}}{M_{lex}(x_1)} - \frac{M_{lex}(x_1)(\sigma_{\max})}{a(\sigma_{\max})}a$$

that satisfies by design $\sigma_{\max} \notin |x|$, so that $x \subset_{lex} M_{lex}(x_1)$. Since $x \in x_1 + A$, this is a clear contradiction with the definition of $M_{lex}(x_1)$: we conclude that $\sigma_{\max} \notin |M_{lex}(x_1)|$. A similar construction assuming $\sigma_{\max} \in |M_{lex}(x_1 + \lambda x_2)|$ or $\sigma_{\max} \in |M_{lex}(x_2)|$ leads to the same contradiction. We conclude that $a = 0$ and $M_{lex}$ is linear. $\square$

## 2.3 Lexicographic optimal homology representatives

We can translate the properties described in Section 2.2 for absolute chains in a complex $K$. This setting corresponds to taking $E = C_k(K)$ and $A = B_k(K)$. We omit for simplicity the exponent of $M_{lex}^{B_k(K)}$. The same properties of existence, uniqueness, and linearity can be deduced for relative chains from Section 2.2 using $E = C_k(K, B)$ and $A = B_k(K, B)$.

The linearity of $M_{lex}$ allows to define the following subspace $Z_k^{\min}(K)$ of $Z_k(K)$, made of chains that are minimal among homologous chains.

$$Z_k^{\min}(K) = \underset{\text{def.}}{M_{lex}(Z_k(K))}$$

The following diagram commutes and implies an isomorphism from $Z_k^{\min}(K)$ to $\mathcal{H}_k(K)$:

<figure><img src="image_3.png" /></figure>

We can now draw a few comparisons between lexicographic and $l^1$ or $l^2$ optimalities. On the one hand, we see that the vector space of lexicographic optimal chains is isomorphic to homology groups. This mimics the property of harmonic forms, which can be defined in Hodge theory as $l^2$ minimal chains in their homology classes. Similar to $M_{lex}$, the map that associates to a chain its unique homologous harmonic form is linear. On the other hand, $l^1$ optimal chains in their homology class have been more intensively studied than their $l^2$ counterpart. This is mainly because $l^1$ minima are sparse and, as such, are visually meaningful geometric representations of corresponding homology classes.

Lexicographic optimality benefits from both properties: the linearity and therefore isomorphism with homology classes of $l^2$ minima, as well as the sparsity of support and geometric meaningfulness of $l^1$ minima.
<figure><img src="image_4.png" /><figcaption>Fig. 2: Illustration of the open surface reconstruction steps. From a set of points and a 1-cycle in the Delaunay 3-complex (a), a representative 2-chain bounding this 1-cycle is computed (b). The lexicographic optimal 2-chain homologous to this representative chain is then computed (c). A point far from the Möbius strip has been added to illustrate the representative chain creation process and better differentiate between the representative and optimal chains.</figcaption></figure>

## 3 Problem statement and algorithmic construction

A practical motivation of this work is the design of an efficient algorithm for open surface reconstruction in codimension 1. Indeed, previous work [10] showed that the following problem of finding a lexicographic optimal chain under imposed boundary could be solved in polynomial time for a generic simplicial complex ($\mathcal{O}(n^3)$ for a complex of size $n$).

**Problem 1** Given a simplicial complex $K$ with a total order on its $k$-simplices and a $(k-1)$-boundary $A$, find the lexicographic optimal chain $\Gamma_{\min}$ bounded by $A$:

$$ \Gamma_{\min} = \min_{\subseteq \text{lex}} \{\Gamma \in \mathbf{C}_k(K) \mid \partial_k \Gamma = A\} $$

For the particular case of chains in codimension 1 of a pseudo-manifold, we derive the following two-step algorithm, illustrated in Figure 2. Given a $(d-2)$-boundary $A$, our approach consists of:

1. constructing a representative $(d-1)$-chain $\Gamma_0$ that satisfies $\partial\Gamma_0 = A$ (detailed in Section 6);

2. finding the lexicographic optimal $(d-1)$-chain homologous to $\Gamma_0$ (detailed in Section 5).

Note that this differs in general from Problem 1, as being homologous implies having the same boundary, but the converse is not always true. The two problems are however equivalent when the complex has trivial homology.

The first part of the approach, finding a representative chain under imposed boundary, can be solved in $\mathcal{O}(n \log n)$ time complexity for the Delaunay complex of size $n$. The main idea of this algorithm is rather intuitive: roughly speaking, given an arbitrary direction in the Delaunay complex, the algorithm
recursively replaces the highest point of the initially given 1-boundary A by a set of edges in the lower link of this vertex. By recording the 2-simplices generated as joins of this highest vertex with each added edge of the lower link, we can construct a 2-chain $\Gamma_0$ which satisfies $\partial\Gamma_0 = A$. The main steps of the algorithm are illustrated in Figure 6 and a result for the Möbius strip can be seen in Figure 2b. As the proof is self-contained and specific to the Delaunay complex, this algorithm will be detailed later on in Section 6.

Instead, the following two sections are focused on the second part of the approach, i.e. computing the lexicographic optimal chain homologous to a given chain.

# 4 Simplicial and Lefschetz duality

Lefschetz duality provides an isomorphism between homology and cohomology groups [13, Chapter 8, §70]. However, for our application, we are more interested in characterizing cycles and boundaries (rather than homology classes) in terms of dual chains. The presentation of this section therefore describes the duality at the chain level. The definitions of this section will be useful in the construction of a quasi-linear time algorithm in codimension 1 in Section 5.

## 4.1 Simplicial duality

Any triangulated manifold $K$ admits a dual polyhedral decomposition. We denote $\tilde{K}$ the cell complex dual to $K$, where $k$-cells are in bijective correspondence with the $(d-k)$-simplices of $K$. A prime example of this duality is Voronoi diagrams, dual to Delaunay triangulations.

For $0 \le k \le d$, denote by $K^{(k)}$ and $\tilde{K}^{(k)}$ the set of $k$-simplices of $K$ and the set of $k$-cells of $\tilde{K}$. For $\sigma, \tau \in K$ with $\dim(\sigma) = \dim(\tau) - 1$ one writes $\sigma \preceq_s \tau$, where $s \in \{-1, 1\}$, when $\sigma$ is a face of $\tau$ and $s \in \{-1, 1\}$ is the sign of $\sigma$ as it appears in $\partial\tau^1$. The duality between $K$ and $\tilde{K}$ means precisely that:

* for $0 \le k \le d$, there is a bijection between $K^{(k)}$ and $\tilde{K}^{(d-k)}$, where the cell dual of the $k$-simplex $\sigma \in K^{(k)}$ is denoted $\tilde{\sigma} \in \tilde{K}^{(d-k)}$,

* for $\sigma, \tau \in K$ such that $\dim(\sigma) = \dim(\tau) - 1$ then:

$$ \sigma \preceq_s \tau \iff \tilde{\tau} \preceq_s \tilde{\sigma} \quad (3) $$

Eq. (3) can be equivalently formulated as saying the matrices of the respective boundary operators $\partial_{C_{k+1}(K)} : C_{k+1}(K) \to C_k(K)$ and $\partial_{C_{d-k}(\tilde{K})} : C_{d-k}(\tilde{K}) \to C_{d-k-1}(\tilde{K})$, expressed in the simplices (or cells) bases, are transpose of each other:

$$ \partial_{C_{d-k}(\tilde{K})} = (\partial_{C_{k+1}(K)})^t $$

<footnote n="1">¹The sign $s$ can be ignored if $\mathbb{F} = \mathbb{Z}_2$</footnote>
## 4.2 Lefschetz duality

For this section, we consider a simplicial complex $K$ triangulating the $d$-sphere $S^d$, and $\tilde{K}$ its dual cell complex$^2$. By considering $k$-chains (respectively $(d-k)$-chains) as vectors expressed in their simplex (resp. cell) bases, we denote by intersection product the bilinear form defined by:

$$ \otimes : \mathbf{C}_k(K) \times \mathbf{C}_{d-k}(\tilde{K}) \to \mathbb{F} \\ (\Gamma, \gamma) \mapsto \Gamma \otimes \gamma = \sum_{\sigma \in K^{(k)}} \Gamma(\sigma) \gamma(\tilde{\sigma}) = \Gamma^t \gamma \quad (4) $$

As shown in Section 4.1, the duality between $K$ and $\tilde{K}$ can be expressed in terms of boundary operators.

$$ \partial_{\mathbf{C}_{d-k}(\tilde{K})} = (\partial_{\mathbf{C}_{k+1}(K)})^t $$

This translates to the following commutativity property for the intersection product.

$$ \forall \Gamma \in \mathbf{C}_{k+1}(K), \forall \gamma \in \mathbf{C}_{d-k}(\tilde{K}), \quad \partial \Gamma \otimes \gamma = (\partial \Gamma)^t \gamma = \Gamma^t (\partial^t \gamma) = \Gamma \otimes \partial \gamma \quad (5) $$

Consider now $B$ a subcomplex of $K$. While $K \setminus B$ is not a simplicial complex in general, because some simplices in $K \setminus B$ may have faces in $B$, by contrast, the set of its dual cells, $\tilde{K} \setminus B$, is a cellular complex. Observe that the set of $k$-simplices in $K \setminus B$, in bijection with their dual $(d-k)$-cells in $\tilde{K} \setminus B$, defines a canonical basis for both $\mathbf{C}_k(K, B)$ and $\mathbf{C}_{d-k}(\tilde{K} \setminus B)$ in which the intersection product $\otimes$ corresponds to the canonical dot product between respective coordinates in $\mathbb{F}^n$, where $n$ is the cardinal of $(\tilde{K} \setminus B)^{(d-k)}$. Identifying a chain $\Gamma \in \mathbf{C}_{d-k}(K, B)$ with the dual element $\Gamma^* : \gamma \mapsto \Gamma \otimes \gamma$, the orthogonal complement can be used to describe duality properties.

**Definition 2** For a vector subspace $V$ of $C_1(\tilde{K} \setminus B)$, $$ V^{\perp} = \{ \Gamma \in C_{d-1}(K, B) \mid \forall \gamma \in V, \Gamma \otimes \gamma = 0 \} $$

Properties of duality between relative 2-chains of $(K, B)$ and 1-chains of the dual $\tilde{K} \setminus B$, illustrated in dimension 3 by Figure 3, can be summarized by the following lemma.

**Lemma 3** Let $K \simeq S^d$ and $B$ a subcomplex of $K$.

$$ \mathbf{Z}_{d-1}(K, B) = \mathbf{B}_1(\tilde{K} \setminus B)^{\perp} \quad \text{and} \quad \mathbf{B}_{d-1}(K, B) = \mathbf{Z}_1(\tilde{K} \setminus B)^{\perp} $$

<footnote>$^2$Note that this section could be generalized to $K$ being an oriented pseudomanifold</footnote>
<figure><img src="image_5.png" /><figcaption>**Fig. 3:** Illustration of the intersection product and Lemma 3 in dimension 3. The pink region corresponds to subcomplex B of the ambient complex K. The intersection product between $\Gamma \in \mathbb{Z}_2(K, B)$ and any $\gamma \in B_1(\tilde{K} \setminus \tilde{B})$ satisfies $\Gamma \otimes \gamma = 0$. The intersection product between $\Gamma' \in \mathbb{Z}_2(K, B)$ and any $\gamma' \in \mathbb{Z}_1(\tilde{K} \setminus \tilde{B})$ also satisfies $\Gamma' \otimes \gamma' = 0$.</figcaption></figure>

*Proof* This is obtained from an elementary property of linear algebra. For a matrix A:

$$ \mathrm{Ker} A = (\mathrm{Im} A^t)^{\perp} \quad \text{and} \quad \mathrm{Im} A^t = (\mathrm{Ker} A)^{\perp} $$

Thanks to Eq. (5), Lemma 3 is derived from previous equations by considering respectively the matrices $\partial_{\mathcal{C}_{d-1}(K,B)}$ and $\partial_{\mathcal{C}_2(\tilde{K} \setminus \tilde{B})}$. $\square$

The intersection product of previous section extends to homology classes. Indeed, for two homologous relative $(d-1)$-cycles $\Gamma, \Gamma' \in \mathbb{Z}_{d-1}(K, B)$, the fact that $\Gamma' - \Gamma$ belongs to $\mathbb{B}_{d-1}(K, B)$ implies, thanks to Lemma 3:

$$ \forall \gamma \in \mathbb{Z}_1(\tilde{K} \setminus \tilde{B}), \quad \Gamma' \otimes \gamma = \Gamma \otimes \gamma $$

Similarly, for two homologous 1-cycles $\gamma, \gamma' \in \mathbb{Z}_1(\tilde{K} \setminus \tilde{B})$:

$$ \forall \Gamma \in \mathbb{Z}_{d-1}(K, B), \quad \Gamma \otimes \gamma' = \Gamma \otimes \gamma $$

The intersection product is therefore independent of the chosen representative of the homology class and extends to a bilinear form on homology groups:

$$ \otimes : \mathcal{H}_{d-1}(K, B) \times \mathcal{H}_1(\tilde{K} \setminus \tilde{B}) \to \mathbb{F} $$

**Lemma 4** The pairing $\otimes : \mathcal{H}_{d-1}(K, B) \times \mathcal{H}_1(\tilde{K} \setminus \tilde{B}) \to \mathbb{F}$ is perfect, which means it induces an isomorphism between $\mathcal{H}_1(\tilde{K} \setminus \tilde{B})$ and the dual of $\mathcal{H}_{d-1}(K, B)$.
# 5 Lexicographic optimal homologous relative chain in codimension 1

This section focuses on solving the problem of finding the lexicographic optimal relative chain homologous to a given chain $\Gamma_0 \in C_{d-1}(K, B)$.

**Problem 2** (Lex-OHRCP) Given a simplicial pair $(K, B)$, and a $(d-1)$-chain $\Gamma_0 \in C_{d-1}(K, B)$, find the lexicographic optimal chain $\Gamma_{\min}$ homologous to $\Gamma_0$:

$$ \Gamma_{\min} =_{def.} M_{lex}^{B_{d-1}(K,B)}(\Gamma_0) = \min_{\subseteq lex} \{\Gamma_0 + b, b \in B_{d-1}(K, B)\} $$

## 5.1 Dual problem formulation

We start by deriving a dual formulation of Problem 2. We consider a simplicial complex $K$ triangulating the $d$-sphere $S^d$, and $\tilde{K}$ its dual cell complex. For a $k$-simplex $\sigma$ of $K$, we denote by $\tilde{\sigma}$ its dual $(d-k)$-cell in $\tilde{K}$.

As seen in Section 4.2, the intersection product allows characterizing homologous chains by verifying their intersection products with dual cycles.

**Lemma 5** (Consequence of Lemma 3) Given $\Gamma, \Gamma_0 \in C_{d-1}(K, B)$
$\Gamma$ homologous to $\Gamma_0 \iff \forall \gamma \in \mathbb{Z}_1(\tilde{K} \setminus \tilde{B}), (\Gamma - \Gamma_0) \otimes \gamma = 0$

We denote by $G_{K\setminus B} = (\mathcal{V}_{K\setminus B}, \mathcal{E}_{K\setminus B})$ the 1-skeleton of the complex $\tilde{K} \setminus \tilde{B}$, where $\mathcal{V}_{K\setminus B}$ and $\mathcal{E}_{K\setminus B}$ are respectively the set of vertices and edges of the graph. Note that $\mathbb{Z}_1(G_{K\setminus B}) = \mathbb{Z}_1(\tilde{K} \setminus \tilde{B})$. We now consider the following graph problem.

**Problem 3** (Dual problem) Given a subgraph $G$ of $G_{\tilde{K} \setminus \tilde{B}}$, with a total order on its edges, and $\Gamma_0 \in C_{d-1}(K, B)$, consider the set:

$$ \Delta_G =_{def.} \{ \Gamma \in C_{d-1}(K, B) \mid \forall \gamma \in \mathbb{Z}_1(G), (\Gamma - \Gamma_0) \otimes \gamma = 0 \} $$

and find the lexicographic optimal chain over this set: $\Gamma_{\min} =_{def.} \min_{\subseteq lex} \Delta_G$.

We have then immediately the following problem equivalency from Lemma 5.

**Lemma 6** Consider $\Gamma_0 \in C_{d-1}(K, B)$ and $(K \simeq S^d, B)$ a simplicial pair. Problem 2 for the simplicial pair $(K, B)$ and $\Gamma_0$ is equivalent to Problem 3 for the graph $G_{K\setminus B}$ and $\Gamma_0$.

We enumerate the (oriented) edges of $\mathcal{E}_{K\setminus B}$ in a decreasing order induced by the total order on the primal $(d-1)$-simplices of $K \setminus B$: $e_1 > e_2 > \dots > e_n$,
where $n$ denotes the number of edges of the graph $G_{K\setminus B}$. We then define the following sequence of graphs:

$$G_i = \underset{\text{def.}}{\left(} \mathcal{V}_{K\setminus B}, \mathcal{E}_i = \{e_j \in \mathcal{E}_{K\setminus B} \mid j \le i\} \right) \quad (6)$$

In particular, $G_0 = (\mathcal{V}_{K\setminus B}, \mathcal{E}_i)$ and $G_n = G_{K\setminus B}$. The following observation shows an important property of the solutions of Problem 3 for this increasing sequence of graphs. We naturally extend the dual notation $\tilde{\cdot}$ to sets of 1-simplices.

**Observation 2** Denote by $\Delta_{G_i}$ the set of Problem 3 associated to some graph $G_i = (\mathcal{V}_{K\setminus B}, \mathcal{E}_i)$ defined in Eq. (6). For $\Gamma \in \mathbf{C}_{d-1}(K, B)$ and $\gamma \in \mathbf{Z}_1(G_i)$,

$$|\Gamma - \Gamma_0| \cap |\tilde{\gamma}| = \emptyset \implies (\Gamma - \Gamma_0) \otimes \gamma = 0$$

The constraints defining the set $\Delta_{G_i}$ rely only on the values of $\Gamma$ on the $(d-1)$-simplices dual to 1-simplices in $\mathcal{E}_i$. The optimal chain on $\Delta_{G_i}$ therefore satisfies:

$$|\min_{\subseteq lex} \Delta_{G_i}| \subset \tilde{\mathcal{E}}_i$$

The minimum of Problem 3 for $G_{K\setminus B}$ can be constructed incrementally by considering the increasing sequence of graphs $(G_i)_{i=0,...,n}$. To this end, we borrow terminology from persistent homology [14, Section VII.1] and qualify edges as positive if their addition creates new cycles in the graph and as negative if their addition merges two connected components.

**Lemma 7** Consider $\Gamma_0 \in \mathbf{C}_{d-1}(K, B)$. Denote by $\Gamma^{(i)}$ and $\Gamma^{(i+1)}$ the respective solutions of Problem 3 for the graphs $G_i$ and $G_{i+1}$ and the chain $\Gamma_0$. Denote by $e_{i+1}$ the edge added to $G_i$ to form $G_{i+1}$.

- If the edge $e_{i+1}$ is negative:

$$\Gamma^{(i+1)} = \Gamma^{(i)}$$

- If the edge $e_{i+1}$ is positive, for any $\gamma_{i+1} \in \mathbf{Z}_1(G_{i+1}) \setminus \mathbf{Z}_1(G_i)$ satisfying $\gamma_{i+1}(e_{i+1}) = 1$,

$$\Gamma^{(i+1)} = \Gamma^{(i)} + \alpha \tilde{e}_{i+1} \text{ with } \alpha = -(\Gamma^{(i)} - \Gamma_0) \otimes \gamma_{i+1}$$

*Proof* A negative edge will kill a connected component but no new cycles will be formed by adding this edge and $\mathbf{Z}_1(G_{i+1}) = \mathbf{Z}_1(G_i)$. We have immediately that $\Gamma^{(i)}$ is solution for $G_{i+1}$.

For a positive edge $e_{i+1}$, a new graph cycle is formed in $G_{i+1}$. In terms of chains, this means $\dim \mathbf{Z}_1(G_{i+1}) = \dim \mathbf{Z}_1(G_i) + 1$, and we can consider a 1-chain $\gamma_{i+1}$ in $\mathbf{Z}_1(G_{i+1}) \setminus \mathbf{Z}_1(G_i)$ satisfying $\gamma_{i+1}(e_{i+1}) = 1$. Let's verify that $\Gamma^{(i)} + \alpha e_{i+1} \in \Delta_{G_{i+1}}$,
with $\alpha = -(\Gamma^{(i)} - \Gamma_0) \otimes \gamma_{i+1}$. Consider any cycle $\gamma$ in $\mathbb{Z}_1(G_{i+1})$ and $\mu = \gamma(e_{i+1})$ its coefficient for the edge $e_{i+1}$. The cycle $\gamma$ can be written as $\gamma' + \mu\gamma_{i+1}$, where $\gamma' = \gamma - \mu\gamma_{i+1}$ is in $\mathbb{Z}_1(G_i)$. The following intersection product along this cycle can then be decomposed as:

$$ (\Gamma^{(i)} + \alpha \tilde{e}_{i+1} - \Gamma_0) \otimes \gamma = (\Gamma^{(i)} - \Gamma_0) \otimes \gamma' + \alpha \tilde{e}_{i+1} \otimes \gamma' + \mu (\Gamma^{(i)} + \alpha \tilde{e}_{i+1} - \Gamma_0) \otimes \gamma_{i+1} $$

By definition of $\Gamma^{(i)}$ as solution of Problem 3 for $G_i$, $(\Gamma^{(i)} - \Gamma_0) \otimes \gamma' = 0$. As $e_{i+1} \notin |\gamma'|$, we also have $\tilde{e}_{i+1} \otimes \gamma' = 0$. Finally, as $\gamma_{i+1}(e_{i+1}) = 1$ and from the definition of $\alpha$, the last term of the sum is also zero:

$$ (\Gamma^{(i)} + \alpha \tilde{e}_{i+1} - \Gamma_0) \otimes \gamma_{i+1} = (\Gamma^{(i)} - \Gamma_0) \otimes \gamma_{i+1} + \alpha \tilde{e}_{i+1} \otimes \gamma_{i+1} = 0 $$

and we have shown that $\Gamma^{(i)} + \alpha \tilde{e}_{i+1} \in \Delta_{G_{i+1}}$. As $\Gamma^{(i+1)}$ is defined as the lexicographic minimum of $\Delta_{G_{i+1}}$, $\Gamma^{(i+1)} \subseteq_{lex} \Gamma^{(i)} + \alpha \tilde{e}_{i+1}$. We have also that $\Gamma^{(i)} \subseteq_{lex} \Gamma^{(i+1)}$ from the inclusion $\Delta_{G_{i+1}} \subseteq \Delta_{G_i}$. Hence, the following bounds for $\Gamma^{(i+1)}$:

$$ \Gamma^{(i)} \subseteq_{lex} \Gamma^{(i+1)} \subseteq_{lex} \Gamma^{(i)} + \alpha \tilde{e}_{i+1} \quad (7) $$

Recall that Observation 2 showed that $|\Gamma^{(i+1)}| \subset \tilde{\mathcal{E}}_{i+1}$. Together with Eq. (7) and the fact that edges are taken in a decreasing order, the supports of $\Gamma^{(i)}$ and $\Gamma^{(i+1)}$ can only differ on $\tilde{e}_{i+1}$. When $\alpha = -(\Gamma^{(i)} - \Gamma_0) \otimes \gamma_{i+1}$ is not zero, $\Gamma^{(i)} \notin \Delta_{G_{i+1}}$. Therefore, the support of $\Gamma^{(i+1)}$ needs to contain $\tilde{e}_{i+1}$ and the uniqueness of the solution from Lemma 1 implies $\Gamma^{(i+1)} = \Gamma^{(i)} + \alpha \tilde{e}_{i+1}$. When $\alpha = -(\Gamma^{(i)} - \Gamma_0) \otimes \gamma_{i+1}$ is zero, we can of course also write $\Gamma^{(i+1)} = \Gamma^{(i)} + \alpha \tilde{e}_{i+1}$. $\square$

Lemma 7 shows that two key elements are required to incrementally construct the solution for Problem 3: tracking connected components in the sequence of graphs $(G_i)_{i=0,...,n}$, to distinguish between positive and negative edges, and computing the coefficient $\alpha$ for any new cycle going through a positive edge. The former requires the classic disjoint-set data structure to keep track of incremental connected components. In the next section, we will show how a small augmentation of this data structure allows us to efficiently compute the latter.

## 5.2 Augmented disjoint-set data structure

Lemma 7 requires, for a positive edge, to compute intersection products along a cycle passing through this edge. The tree structure of the classic disjoint-set data structure [15] can be modified to efficiently compute these intersection products.

In this augmented version of the disjoint-set structure, a tree node consists of a parent pointer to an ancestor and a value in $\mathbb{F}$, respectively denoted by parent and value in functions of Algorithm 1. The three main operations of the disjoint-set structure (MakeSet, FindSet and LinkSet) need to be modified to take into account this additional value in $\mathbb{F}$. We describe these operations in Algorithm 1 and illustrate them in Figure 4. In all that follows, we assume that all calls to LinkSet* are valid, i.e. its inputs are two distinct root elements.

Our interest for this data structure is best explained by the following property:
<figure><img src="image_6.png" /><figcaption>**Fig. 4:** Illustration of operations on the augmented disjoint-set. On the left, the **FindSet*** call on the node element 3 will return the root 5 with a value of 4. On the right, the operation **LinkSet*** (7, 5, 2) was called.</figcaption></figure>

**Lemma 8 (Value Stability)** After calling **LinkSet***($r_1, r_2, \alpha$) on two distinct root elements $r_1$ and $r_2$ with $\alpha \in \mathbb{F}$, any following calls to **FindSet*** on $r_1$ and $r_2$ (even after other **LinkSet*** operations) return values $g_1$ and $g_2$ that satisfy:

$$g_1 - g_2 = \alpha$$

*Proof* As written in Algorithm 1, $r_2$ is the new root element of the set. Right after calling **LinkSet***($r_1, r_2, \alpha$), the value returned by the **FindSet*** operations on $r_1$ and $r_2$ are respectively $\alpha$ and $0_{\mathbb{F}}$.

It is clear that any subsequent call to **LinkSet*** that does not involve $r_2$ will have no impact on the returned values. Otherwise, if a call to **LinkSet*** is made between $r_2$ and another root element $r_3$ with a value $\beta \in \mathbb{F}$, calls to **FindSet*** on $r_1$ and $r_2$ will reflect that change but not affect the difference:

$$g_1 - g_2 = (\alpha + \beta) - \beta = \alpha$$

□

Note that, with regard to Lemma 8, calling **LinkSet***($r_1, r_2, \alpha$) or **LinkSet***($r_2, r_1, -\alpha$) is equivalent, even for $\mathbb{F} \neq \mathbb{Z}_2$.

Two strategies are used in the standard disjoint-set structure to make it asymptotically optimal [16]: *path compression* and *union by rank*. With path compression, nodes explored during a **FindSet** operation are updated, creating shorter paths to the root element. This can be done for example by replacing every node's pointer to its grandparent. Union by rank is a strategy to avoid having tall trees in the structure, which would be more costly to traverse during **FindSet** operations. Each set has an additional integer called rank which essentially allows to compare the size of two sets. During a **LinkSet** operation, we always want the set with lower rank to point to the root element of the set with higher rank. In case of equality, the root element of one of the two sets is arbitrarily chosen as the new root of the union and the rank of this union set is incremented by one. The reader can verify that these two strategies making the standard disjoint-set structure asymptotically optimal
<caption>**Algorithm 1** Augmented disjoint-set operations</caption>

**function** MAKESET*(x)
  x.parent = x
  x.value = 0<sub>F</sub>
**end function**

**function** FINDSET*(x)
  g = 0<sub>F</sub>
  **while** x ≠ x parent **do**
    g = g + x.value
    x = x parent
  **end while**
  **return** (x, g)
**end function**

**function** LINKSET*(r<sub>1</sub>, r<sub>2</sub>, δ ∈ F)*
  // r<sub>1</sub>, r<sub>2</sub> are root elements
  r<sub>1</sub>.parent = r<sub>2</sub>
  r<sub>1</sub>.value = δ
**end function**

can still be used in this augmented version without breaking the value stability of Lemma 8. During path compression, the *value* associated with a node needs to be updated by summing all coefficients on the compressed path starting from this node. During union by rank, the given value in the **LinkSet*** operation has to be set to its opposite if the largest set corresponds to the first given root element. The structure makes exactly the same number of addition as the tree height when calling the **FindSet*** operation. Therefore, the complexity of its augmented version is $c\alpha(n)$, where $n$ is the number of sets, $\alpha$ is the inverse Ackermann function and $c$ denotes the cost of addition in $F$.

## 5.3 Algorithmic solution

In this section, from the dual formulation presented in Section 5.1 and with the help of the augmented disjoint-set structure described in Section 5.2, we present an algorithmic solution for Problem 2.

**Lemma 9** *Taking as inputs* $\Gamma_0 \in C_{d-1}(K, B)$ and the graph $G_{K\setminus B}$ with edges sorted in decreasing order along the total order defined on $(d-1)$-simplices, Algorithm 2 solves Problem 2 in $O(|c\alpha(n)|)$ time complexity, where $n$ is the number of edges in the graph $G_{K\setminus B}$, $\alpha$ the inverse Ackermann function and $c$ the cost of addition in $F$.*

*Proof* Algorithm 2 is an iterative application of Lemma 7. Every edge of the graph is considered in decreasing order along the total order on $(d-1)$-simplices, which
<caption>**Algorithm 2** Lexicographic optimal homologous relative chain</caption>

**Inputs:** $G = (\mathcal{V}_{K\setminus B}, \mathcal{E}_{K\setminus B})$ with $\mathcal{E}_{K\setminus B} = \{e_i, i = 1, \dots, n\}$ in decreasing order, $\Gamma_0 \in \mathbf{C}_{d-1}(K, B)$.
**Output:** $\Gamma_{\min} \in \mathbf{C}_{d-1}(K, B)$, lexicographic optimal relative chain homologous to $\Gamma_0$.
$\Gamma_{\min} \leftarrow 0$
**for** $v \in \mathcal{V}_{K\setminus B}$ **do**
  **MAKESET**\*(v)
  **end for**
  **for** $e \in \mathcal{E}_{K\setminus B}$ **in** decreasing order **do**
    $e = (v_1, v_2) \in \mathcal{V}_{K\setminus B} \times \mathcal{V}_{K\setminus B}$
    $(r_1, g_1) \leftarrow \text{FINDSET}^{*}(v_1)$
    $(r_2, g_2) \leftarrow \text{FINDSET}^{*}(v_2)$
    $\alpha = \Gamma_0(\tilde{e}) + g_2 - g_1$
    **if** $r_1 = r_2$ **then**
      $\Gamma_{\min} \leftarrow \Gamma_{\min} + \alpha \cdot \tilde{e}$
    **else**
      $\text{LINKSET}^{*}(r_1, r_2, \alpha)$
    **end if**
  **end for**

corresponds to the graph filtration $(G_i)_{i=0,\dots,n}$. At each iteration $i$, we will show by induction that the following two invariants are satisfied:

- $\Gamma_{\min}$ is the solution of Problem 3 for $G_i$,

- for any negative edge $e = (v_1, v_2) \in \mathcal{E}_i$, the values $g_1$ and $g_2$ returned by calling the **FindSet**\* operations on $v_1$ and $v_2$ satisfy: $g_1 - g_2 = \Gamma_0(\tilde{e})$.

Sets are created using the **MakeSet**\* operation for each vertex in $\mathcal{V}_{K\setminus B}$. Initially, $\Gamma_{\min} = 0$, which corresponds to the solution of Problem 3 for $G_0$. As $\mathcal{E}_0 = \emptyset$, the invariant on the augmentation part of the disjoint-set structure is also satisfied.

At an iteration $i$, we consider the edge $e_{i+1} = (v_1, v_2)$ and suppose $\Gamma_{\min}$ is the solution of Problem 3 for graph $G_i$. We also assume the invariant on the augmented disjoint-set is satisfied. Following Lemma 7, we first determine whether the edge $e_{i+1}$ is positive or negative: this is done by calling the **FindSet**\* operation on both vertices $v_1$ and $v_2$ and testing if the returned root elements $r_1$ and $r_2$ are equal or not.

If the edge is negative, i.e. $r_1 \neq r_2$, Lemma 7 shows $\Gamma_{\min}$ is still the solution of Problem 3 for graph $G_{i+1}$. The **LinkSet**\* operation is then used to connect the sets represented by root elements $r_1$ and $r_2$, as well as updating the value between the sets. The updated data structure is illustrated in Figure 5. Indeed, denote by $g_1$ and $g'_1$ (resp. $g_2$ and $g'_2$) the values obtained by calling the **FindSet**\* operation on $v_1$ (resp. $v_2$) before and after having called this **LinkSet**\* operation. We now have:

$$g'_1 - g'_2 = g_1 + \alpha - g_2 = g_1 + (\Gamma_0(\tilde{e}_{i+1}) + g_2 - g_1) - g_2 = \Gamma_0(\tilde{e}_{i+1})$$

We have thus shown that the invariant is true for the negative edge $e_{i+1}$ and, thanks to Lemma 8, we know it is still true for all other negative edges.
<figure><img src="image_7.png" /><figcaption>**Fig. 5:** Illustration of the augmented disjoint-set data structure after considering an edge $e_{i+1} = (v_1, v_2)$. The value $g_1$ (resp. $g_2$) corresponds to the values returned by calling the **FindSet*** operations on $v_1$ (resp. $v_2$). The blue dashed edge is not present in the disjoint-set structure but illustrates the value that we would like to get as a difference between calls to **FindSet*** on $v_1$ and $v_2$ after update.</figcaption></figure>

If the edge is positive, i.e. $r_1 = r_2$, we know there is an oriented path $p$ of negative edges from $v_1$ to $v_2$ in $\mathcal{E}_i$. Using the invariant on the augmented disjoint-set for all edges on this path, $g_1 - g_2$ will represent the intersection product with $\Gamma_0$ along this path:

$$g_1 - g_2 = \Gamma_0 \otimes p$$

We can now create the cycle $\gamma_{i+1} = e_{i+1} - p \in \mathbb{Z}_1(G_{i+1}) \setminus \mathbb{Z}_1(G_i)$ that satisfies $\gamma_{i+1}(e_{i+1}) = 1$ and use it to compute the value of $\alpha$ from Lemma 7:

$$\alpha = -(\Gamma_{\min} - \Gamma_0) \otimes \gamma_{i+1}$$

For any negative edge $e$ in $G_i$, we know that $\Gamma_{\min}(\tilde{e}) = 0$ as well as $\tilde{e}_{i+1} \notin |\Gamma_{\min}|$ such that:

$$\alpha = \Gamma_0 \otimes (e_{i+1} - p) = \Gamma_0(\tilde{e}_{i+1}) + g_2 - g_1$$

The chain $\Gamma_{\min}$ is updated in consequence to become the minimum of Problem 3 for graph $G_{i+1}$.

The output of the algorithm is therefore the solution of Problem 3 for the whole graph $G_n$. Iterating over all edges of the graph while using disjoint-set operations leads to a $O(|cn\alpha(n)|)$ complexity. □

Note that this complexity is reached using sorted edges of $G$ as input, giving an $O(n \ln n)$ complexity to the whole algorithm.

# 6 Representative chain in the Delaunay 3-complex

As detailed in Section 3, to compute a lexicographic optimal 2-chain bounded by a given 1-boundary, a critical first step is to compute a "representative" 2-chain bounded by the given boundary. In this section, which is independent
<figure><img src="image_8.png" /><figcaption>**Fig. 6:** Left: the lower link *LL* of *a* with the two adjacent edges of *a* in *A*. Center: a path in *LL* (in orange) between the two adjacent vertices of *a* in *A*. Right: triangles created as joins of *a*. The path in *LL* between the two adjacent vertices replaces the edges adjacent to *a* in *A* (in red).</figcaption></figure>

of the rest of the paper, we describe Algorithm 3 that does exactly that in the Delaunay complex. For simplicity, the algorithm assumes the chain coefficient is $\mathbb{F} = \mathbb{Z}_2$, but the approach extends similarly to an arbitrary coefficient field. The algorithm is also given in detail for a 3-dimensional complex as this is our main motivation in applications. However, the algorithm can be extended to arbitrary dimension, by adapting the same recursion on the dimension as for [11, proof of Lemma 10].

**Observation 3** The 1-homology of the Delaunay 3-complex is trivial, therefore all cycles are boundaries, which implies the existence of a representative chain bounding any cycle in the Delaunay complex.

## 6.1 Lower link of a vertex in the 3D Delaunay complex

In all that follows, **P** denotes a set of points in $\mathbb{R}^3$ satisfying the following generic condition. In practice, non-generic configurations can be solved by simulation of simplicity [17].

**Condition 1** *No pair of vertices in P have the same z-coordinate.*

We recall the notions of link and lower link.

**Definition 3** (Link of a simplex) The link $lk_K(\tau)$ of a simplex $\tau$ in a simplicial complex $K$ is the simplicial complex made of all simplices $\sigma \in K$ such that $\tau \cup \sigma \in K$ and $\tau \cap \sigma = \emptyset$.

**Definition 4** (Lower link of a vertex) The lower link $llk_K(a)$ of a vertex $a \in P$ is the simplicial complex made of all simplices in the link $lk_K(a)$ of $a$ whose vertices have all their $z$-coordinates smaller than the $z$-coordinate of $a$.
<figure><img src="image_9.png" /><figcaption>**Fig. 7:** A vertex in a two-dimensional Delaunay complex (left), its link (center) and lower link (right).</figcaption></figure>

Figure 7 illustrates the definitions of link and lower link in a Delaunay 2-complex. The lower link in the Delaunay 3-complex is also illustrated in Figure 6.

Recall that a topological space and in particular a simplicial complex is said to be **contractible** if it has the homotopy type of a point. In particular, a contractible simplicial complex $K$ is connected, which means that any pair of vertices in $K$ can be connected by a path of edges in $K$.

Algorithm 3 relies on the fact that, in a Delaunay complex, the lower link of a vertex is either empty or contractible.

**Lemma 10** Let $\mathcal{D}\mathcal{e}\mathcal{l}(\mathbf{P})$ be the Delaunay complex of a set of vertices $\mathbf{P}$ in $\mathbb{R}^3$ satisfying Condition 1 and $a \in \mathbf{P}$ a vertex of the complex.

- the lower link $\mathrm{lk}_{\mathcal{D}\mathcal{e}\mathcal{l}(\mathbf{P})}(a)$ is empty if and only if vertex $a$ has minimal $z$-coordinate in $\mathbf{P}$,

- if the $z$-coordinate of $a$ is not minimal in $\mathbf{P}$, $\mathrm{lk}_{\mathcal{D}\mathcal{e}\mathcal{l}(\mathbf{P})}(a)$ is contractible.

*Proof* Denote by $a_z$ the $z$-coordinate of $a$. By definition of the Delaunay triangulation and of $\mathrm{lk}_{\mathcal{D}\mathcal{e}\mathcal{l}(\mathbf{P})}(a)$, there is a one-to-one correspondence between the vertices in $\mathrm{lk}_{\mathcal{D}\mathcal{e}\mathcal{l}(\mathbf{P})}(a)$ and the set of (possibly unbounded) facets contributing to the boundary of the Voronoi cell of $a$. By definition, a vertex $v$ with $z$-coordinate $v_z$ is in the lower link of $a$ if and only if its Voronoi cell has a common boundary with the Voronoi cell of $a$ and $v_z < a_z$. It follows that the Voronoi cell of $a$ is contained in the half-space containing $a$ and bounded by the plane bisector of $a$ and $v$. Such a vertex exists if and only if the vertical half-line starting at $a$ and pointing toward negative $z$ is not contained in the Voronoi cell of $a$. One can see that the vertical half-line starting at $a$ and pointing toward negative $z$ is contained in the Voronoi cell of $a$ if and only if $a$ has minimal $z$ in $V$ and the first statement is proven.

The lower envelope of the Voronoi cell of $a$ is the union of the facets dual to edges connecting $a$ and a vertex in the lower link of $a$. When this lower envelope is not empty, its projection on the horizontal plane is a homeomorphism with a convex two-dimensional polytope. This lower envelope is therefore contractible. Since the lower link of $a$ is the nerve of the set of facets in the lower envelope of the Voronoi cell, the second statement follows from the nerve theorem. $\square$
## 6.2 Algorithmic description

The discussion of Algorithm 3 is split in two: this section will prove the correctness of the algorithm and describe succinctly each of its subroutines, while the complexity is left to the next section. We denote by $\lor$ the join operator on simplices, corresponding to the union for disjoint abstract simplices. In particular, for two 0-simplices $a, v$, $a \lor v$ denotes the 1-simplex $[a, v]$. For a 0-simplex $a$ and a 1-simplex $e = [e_1, e_2]$, $a \lor e$ denotes the 2-simplex $[a, e_1, e_2]$. This operator extends linearly to chains.

<caption>**Algorithm 3** Finding a set of triangles for a given boundary</caption>

**Inputs:** $\mathcal{D}el(\mathbf{P})$ a Delaunay complex and a 1-cycle $A_0 \in \mathbb{Z}_1(\mathcal{D}el(\mathbf{P}); \mathbb{Z}_2)$
**Output:** A 2-chain $\Gamma_0 \in \mathbb{C}_2(\mathcal{D}el(\mathbf{P}); \mathbb{Z}_2)$ satisfying $\partial\Gamma_0 = A_0$
$\Gamma_0 \leftarrow 0$
$A \leftarrow A_0$
**while** $A \neq 0$ **do**
  $a \leftarrow \text{GETHIGHEST VERTEX}(A)$
  $V_a \leftarrow \text{GET ADJACENT VERTICES}(a, A)$
  $LL \leftarrow \text{GET LOWER LINK}(a, \mathcal{D}el(\mathbf{P}))$
  $E \leftarrow \text{GET EDGES CONNECTING}(V_a, LL)$
  **for** $v \in V_a$ **do**
    $A \leftarrow A + a \lor v$
  **end for**
  **for** $e \in E$ **do**
    $A \leftarrow A + e$
    $\Gamma_0 \leftarrow \Gamma_0 + a \lor e$
  **end for**
  **end while**

**Lemma 11** Given a Delaunay complex $K = \mathcal{D}el(\mathbf{P})$ of a set of points $\mathbf{P} \subset \mathbb{R}^3$ satisfying Condition 1 and a 1-cycle $A_0 \in \mathbb{Z}_1(K; \mathbb{Z}_2)$, Algorithm 3 computes a 2-chain $\Gamma_0 \in \mathbb{C}_2(K; \mathbb{Z}_2)$ such that $\partial\Gamma_0 = A_0$.

*Proof* We verify immediately that with the algorithm's initialization of $\Gamma_0$, if $A_0$ is empty, the algorithm returns **0**, and the property $\partial\Gamma_0 = A_0$ is verified.

The following invariants are shown at each iteration of the while loop:

* $\partial\Gamma_0 = A_0 + A$

* $A$ is a cycle and the $z$-coordinate of its highest vertex decreases,

The first invariant will imply that, if the algorithm terminates with $A = 0$, we have that $\partial\Gamma_0 = A_0$. The second invariant implies that the algorithm must terminate.

We now describe the operations performed inside the while loop. Figure 6 illustrates one iteration of this loop. The procedure `GetHighestVertex(A)` returns $a$,
the vertex in an edge in A with the maximal z-coordinate. Since A is a cycle, an even number of edges of A connects a with the set $V_a$ of vertices in the link $lk_{Del(P)}(a)$ of a. This set is returned by the procedure **GetAdjacentVertices**(a, A). The fact that a is the highest vertex in A implies that the set $V_a$ is a subset of the vertices of lower link $lk_{Del(P)}(a)$. $V_a$ is also non-empty and has even cardinality. As A is not zero, it must contain at least 2 distinct vertices and therefore, its highest vertex a cannot be the lowest vertex in $Del(P)$. Lemma 10 asserts then that the lower link of a is non-empty and contractible, proving as a consequence the existence of a 1-chain E bounded by the 0-chain formed by the even set of vertices in $V_a$. The procedure **GetLowerLink**(a, $Del(P)$) returns the 1-skeleton LL of the lower link of a in $Del(P)$. **GetEdgesConnecting**(V_a, LL) uses this 1-skeleton LL to construct a 1-chain $E \in C_1(LL; Z_2)$ that satisfies $\partial E = V_a$.

The main step of the algorithm consists in replacing the edges connecting a in A by the edges on this chain E and adding, for each edge e of E, the corresponding triangle $a \vee e$ in $\Gamma_0$. The following 2-chain is added to $\Gamma_0$:

$$ \sum_{e \in E} a \vee e \qquad (8) $$

and its boundary can be evaluated as:

$$ \partial(\sum_{e \in E} a \vee e) = \sum_{e \in E} (e + a \vee \partial e) = E + a \vee \partial E = E + a \vee V_a \qquad (9) $$

From Eq. (9), the boundary of the 2-chain added to $\Gamma_0$ corresponds to the 1-chain added to A. This means if the invariant $\partial \Gamma_0 = A_0 + A$ was satisfied at the previous iteration, it remains true after additions to $\Gamma_0$ and A: the first invariant is therefore shown. As A is initialized to $A_0$ and is updated by adding a boundary, A remains a cycle at each step. Also, all edges connecting a are removed from A and the added edges are in the lower link $lk_{Del(P)}(a)$ of a. This shows the second invariant. $\square$

## 6.3 Algorithmic complexity

This section will only outline the three key ingredients that allow deriving the complexity of this algorithm. A complete proof can be found in Appendix B.

**Lemma 12** Under Condition 1, Algorithm 3 in the Delaunay complex $Del(P)$ can be implemented in $O(n \log n)$ time complexity, where n is the size of the complex $Del(P)$.

Firstly, by maintaining a total ordering of the edges in the (evolving) chain A, a trivial implementation of the procedures **GetHighestVertex**(A) and **GetAdjacentVertices**(a, A) allows a total cost of $O(n \log n)$ for all the calls of these procedures in the whole algorithm. This is further detailed in Appendix B.1.

Secondly, a single total ordering of the set of triangles in $Del(P)$ as an $O(n \log n)$ preprocessing allows to implement the procedure **GetLowerLink**(a, $Del(P)$) in such a way that the sequence of all the calls to the procedure boils down to a single $O(n)$ pass through this ordered list of
triangles. Therefore, including the preprocessing, the calls to **GetLower-Link**($a$, $Del(P)$) are performed at a total cost of $O(n \log n)$. Please see Appendix B.2 for more details.

Finally, Appendix B.3 describes the implementation of the procedure **Get-EdgesConnecting**($V_a$, $LL$). This starts by creating a spanning tree $T$ in the lower link $LL$, at a cost of $O(m)$, where $m$ is the size of $LL$. It is then possible to compute a 1-chain with boundary $V_a$ in $T$ at a cost of $O(m)$ (Algorithm 6). Although the lower links partially overlap, all simplices of the form $a \lor \sigma$, where $a$ is a vertex of $Del(P)$ and $\sigma \in \text{llk}_{Del(P)}(a)$ are pairwise distinct. Therefore, the sum of the sizes of all lower links is $O(n)$. The total cost of this implementation of **GetEdgesConnecting**($V_a$, $LL$) is $O(n)$.

# 7 Homology representatives and critical basis

In Section 2.3, we showed that the application $M_{lex}$, associating to a simplicial cycle its lexicographic optimal homologous cycle, is linear and induces an isomorphism between the space of lexicographic optimal cycles $Z_k^{\min}(K)$ and homology groups of the complex $\mathcal{H}_k(K)$. This section intends to define a canonical basis of this space of lexicographic optimal cycles that we call *critical basis* and details algorithms for its computation. This construction has strong connections with algorithms used in persistent homology [14]. In particular, it rediscover a variation of matrix reduction, that we have named *total reduction*, but is also known as *exhaustive* or *full* reduction algorithm in previous works [18–20].

Besides highlighting connections with persistent homology, this basis is also motivated by applications in open surface reconstruction. In particular, we hope that the lexicographic optimality of elements in the critical basis leads to them not having too many overlapping supports between each other. In experiments described in (Section 8.2), combining critical basis with a boundary detection algorithm will prove to be an interesting strategy to tackle difficult open surface reconstruction scenarios.

## 7.1 Critical basis of cycles

The definition of the critical basis is only given explicitly for the absolute space $Z_k^{\min}(K)$, but the same construction applies in the context of relative chains for $Z_k^{\min}(K, B)$. The name *critical basis* comes from the fact each basis vector will be associated with a critical simplex.

**Definition 5 (Critical simplex)** For $\Gamma \in Z_k^{\min}(K)$, the critical simplex

$$ \text{crit}(\Gamma) = \underset{\text{def.}}{\max} |\Gamma| $$

is the maximal $k$-simplex in the support $|\Gamma|$ of $\Gamma$.
**Definition 6** (Critical basis) We say that $\mathbf{b} = (\mathbf{b}_1, \dots, \mathbf{b}_m) \in (\mathbf{Z}_k^{\min}(K))^m$ is a critical basis of $\mathbf{Z}_k^{\min}(K)$ if and only if, for $0 \le i \le m-1$:

$$ \mathbf{b}_{i+1} = \min_{\subseteq lex} \left\{ \Gamma \in \mathbf{Z}_k^{\min}(K; \mathbb{F}) \mid \Gamma \notin \operatorname{span}(\mathbf{b}_1, \dots, \mathbf{b}_i) \text{ and } \Gamma(\operatorname{crit}(\Gamma)) = 1 \right\} $$

with $\operatorname{span}(\emptyset) = \{0\}$. When $\mathbb{F} = \mathbb{Z}_2$, the condition $\Gamma(\operatorname{crit}(\Gamma)) = 1$ is unnecessary.

**Lemma 13** *The critical basis is canonical, in other words there is a unique ordered sequence $\mathbf{b} = (\mathbf{b}_1, \dots, \mathbf{b}_m)$ satisfying Definition 6.*

*Proof* Assume, for $i \le m$, the first $i-1$ critical basis elements have been constructed, and denote $S_{i-1} = \operatorname{span}(\mathbf{b}_1, \dots, \mathbf{b}_{i-1})$, with $S_0 = \{0\}$. Since the dimension of $\mathbf{Z}_k^{\min} = \mathbf{Z}_k^{\min}(K)$ is $m > i-1$, there is at least one chain in $\mathbf{Z}_k^{\min} \setminus S_{i-1}$, and the number of possible supports being finite, a minimum among them exists. From Observation 1, two lexicographic minima of $\mathbf{Z}_k^{\min} \setminus S_{i-1}$ must have the same support. Consider, for a contradiction, two such minima $\Gamma_1 \ne \Gamma_2$ with $\Gamma_1(\operatorname{crit}(\Gamma_1)) = \Gamma_2(\operatorname{crit}(\Gamma_2)) = 1$.

One has $|\Gamma_1| = |\Gamma_2|$ so that $\operatorname{crit}(\Gamma_1) = \operatorname{crit}(\Gamma_2)$. Take $\sigma \in |\Gamma_1|$ such that $\Gamma_1(\sigma) \ne \Gamma_2(\sigma)$ and construct the $k$-cycle

$$ \Gamma = \underset{\text{def.}}{\frac{1}{\Gamma_2(\sigma) - \Gamma_1(\sigma)}} (\Gamma_2(\sigma) \Gamma_1 - \Gamma_1(\sigma) \Gamma_2) $$

Observe that $\Gamma$ satisfies $\Gamma(\operatorname{crit}(\Gamma)) = \Gamma(\operatorname{crit}(\Gamma_1)) = 1$ and $\Gamma(\sigma) = 0$. As $|\Gamma| \subset |\Gamma_1| \setminus \{\sigma\}$, $\Gamma$ is strictly smaller for the lexicographic order $\subseteq_{lex}$ than $\Gamma_1$. If $\Gamma \notin S_{i-1}$, this is an immediate contradiction with the optimality of $\Gamma_1$. Otherwise, if $\Gamma \in S_{i-1}$, we can again consider an element $\sigma' \in |\Gamma| \subset |\Gamma_1|$ and construct

$$ \Gamma' = \underset{\text{def.}}{\frac{1}{\Gamma(\sigma') - \Gamma_1(\sigma')}} (\Gamma(\sigma') \Gamma_1 - \Gamma_1(\sigma') \Gamma) $$

which is smaller than $\Gamma_1$ since $|\Gamma'| \subset |\Gamma_1| \setminus \{\sigma'\}$ and $\Gamma' \notin S_{i-1}$, being the sum of $\Gamma_1 \notin S_{i-1}$ and $\Gamma \in S_{i-1}$. We have again a contradiction. $\square$

We give two essential properties of critical bases.

**Lemma 14** For any $i, j = 1, \dots, m$:

$$ i \le j \implies b_i \subseteq_{lex} b_j \qquad (10) $$

$$ \mathbf{b}_j(\operatorname{crit}(\mathbf{b}_i)) = \delta_{ij} \qquad (11) $$

where $\delta_{ij}$ is the Kronecker delta.

*Proof* The first equation is an immediate consequence of the definition of the critical basis elements as minima over an inclusion decreasing sequence of sets. One has also immediately that $\mathbf{b}_i(\operatorname{crit}(\mathbf{b}_i)) = 1$. The following property

$$ j < i \implies \mathbf{b}_j(\operatorname{crit}(\mathbf{b}_i)) = 0 $$
is verified as, if this was not the case, then $\mathbf{b}_j(\mathrm{crit}(\mathbf{b}_i)) \mathbf{b}_i - \mathbf{b}_j$ would be strictly smaller than $\mathbf{b}_i$ and not in $\mathrm{span}(\mathbf{b}_1, \dots, \mathbf{b}_{i-1})$, a contradiction with the minimality of $\mathbf{b}_i$. Symmetrically, a similar argument holds to show that

$$j > i \implies \mathbf{b}_j(\mathrm{crit}(\mathbf{b}_i)) = 0$$

as, if this was not the case, then $\mathbf{b}_j - \mathbf{b}_j(\mathrm{crit}(\mathbf{b}_i)) \mathbf{b}_i$ would be strictly smaller than $\mathbf{b}_j$ and not in $\mathrm{span}(\mathbf{b}_1, \dots, \mathbf{b}_{j-1})$, contradicting the minimality of $\mathbf{b}_j$. $\square$

It follows that, for $i = 1, \dots, m$, $\Gamma \in \mathrm{span}(\mathbf{b}_1, \dots, \mathbf{b}_{i-1}) \implies \Gamma(\mathrm{crit}(\mathbf{b}_i)) = 0$ and therefore:

$$\{ \Gamma \in \mathbb{Z}_k^{\mathrm{min}}(K), \Gamma(\mathrm{crit}(\mathbf{b}_i)) = 1 \} \subset \mathbb{Z}_k^{\mathrm{min}}(K) \setminus \mathrm{span}(\mathbf{b}_1, \dots, \mathbf{b}_{i-1})$$

Since $\mathbf{b}_i$ is in the first set and, by definition, minimum of the second set, one has:

**Observation 4** For $i = 1, \dots, m$:

$$\mathbf{b}_i = \min_{\subseteq lex} \{ \Gamma \in \mathbb{Z}_k^{\mathrm{min}}(K), \Gamma(\mathrm{crit}(\mathbf{b}_i)) = 1 \}$$

## 7.2 Computation of a critical basis

We now bridge the gap between optimal representatives in $\mathbb{Z}_k^{\mathrm{min}}(K)$ and the critical basis of $\mathbb{Z}_k^{\mathrm{min}}(K)$, allowing to construct the critical basis from any basis of $\mathbb{Z}_k^{\mathrm{min}}(K)$.

**Lemma 15** Consider a basis $(\Gamma_i)_{i=1,\dots,m}$ of $\mathbb{Z}_k^{\mathrm{min}}(K)$ that satisfies for all $i, j = 1, \dots, m$

$$\left\{ \begin{array}{l} \Gamma_i(\mathrm{crit}(\Gamma_i)) = 1 \\ i \le j \implies \Gamma_i \subseteq_{lex} \Gamma_j \\ i \ne j \implies \mathrm{crit}(\Gamma_i) \ne \mathrm{crit}(\Gamma_j) \end{array} \right. \qquad (12)$$

The critical basis of $\mathbb{Z}_k^{\mathrm{min}}(K)$ can be constructed, for all $i = 1, \dots, m$, as

$$\mathbf{b}_i = \min_{\subseteq lex} \Gamma_i + \mathrm{span}(\Gamma_1, \dots, \Gamma_{i-1}) \qquad (13)$$

*Proof* By writing an element $\mathbf{b}_i$ in the basis $(\Gamma_j)_{j=1,\dots,m}$, the third property of Eq. (12) requires that the critical simplex of $\mathbf{b}_i$ corresponds to a critical simplex of one element of the basis $(\Gamma_j)_{j=1,\dots,m}$. Therefore, the critical simplices of $(\mathbf{b}_i)_{i=1,\dots,m}$ form a subset of the critical simplices of $(\Gamma_i)_{i=1,\dots,m}$, with the same cardinality. This implies that the set of critical simplices is the same between $(\mathbf{b}_i)_{i=1,\dots,m}$ and $(\Gamma_i)_{i=1,\dots,m}$, and in the same order thanks to the second property of Eq. (12) and Lemma 14. For $i = 1, \dots, m$, we have:

$$\mathrm{crit}(\Gamma_i) = \mathrm{crit}(\mathbf{b}_i)$$
We now show Eq. (13). Denote by

$$ \Gamma_i^{\min} = \min_{\substack{\Gamma_i \\ \subseteq lex}} \Gamma_i + \operatorname{span}(\Gamma_1, \dots, \Gamma_{i-1}) $$

Any element $\Gamma$ of the set $\Gamma_i + \operatorname{span}(\Gamma_1, \dots, \Gamma_{i-1})$ satisfies $\Gamma(\operatorname{crit}(\mathbf{b}_i)) = \Gamma(\operatorname{crit}(\Gamma_i)) = 1$ as $\Gamma_i(\operatorname{crit}(\Gamma_i)) = 1$ (first condition of Eq. (12)) and, from the two last conditions of Eq. (12), for any $j < i$, $\operatorname{crit}(\Gamma_j) < \operatorname{crit}(\Gamma_i)$ therefore $\Gamma_j(\operatorname{crit}(\Gamma_i)) = 0$. We have thus that:

$$ \Gamma_i + \operatorname{span}(\Gamma_1, \dots, \Gamma_{i-1}) \subset \{ \Gamma \in \mathbb{Z}_k^{\min}(K), \Gamma(\operatorname{crit}(\mathbf{b}_i)) = 1 \} $$

and from Observation 4,

$$ \mathbf{b}_i \subseteq lex \Gamma_i^{\min} $$

Next, we write $\mathbf{b}_i$ in the basis $(\Gamma_j)_{j=1,\dots,m}$ of $\mathbb{Z}_k^{\min}(K)$:

$$ \mathbf{b}_i = \sum_{j=1}^{m} \lambda_j \Gamma_j $$

From the third condition of Eq. (12), we have that:

$$ \operatorname{crit}(\mathbf{b}_i) = \max \{ \operatorname{crit}(\Gamma_j), \forall 1 \le j \le m \mid \lambda_j \ne 0 \} $$

As $\operatorname{crit}(\mathbf{b}_i) = \operatorname{crit}(\Gamma_i)$, this implies that $\lambda_j = 0$ for any $j > i$ and thus $\mathbf{b}_i \in \Gamma_i + \operatorname{span}(\Gamma_1, \dots, \Gamma_{i-1})$ resulting in:

$$ \Gamma_i^{\min} \subseteq lex \mathbf{b}_i $$

We have therefore that $|\Gamma_i^{\min}| = |\mathbf{b}_i|$ from Observation 1. Suppose for a contradiction that $\Gamma_i^{\min} \ne \mathbf{b}_i$ and consider $\sigma \in |\Gamma_i^{\min} - \mathbf{b}_i|$. The following chain

$$ \Gamma = \Gamma_i^{\min} - \frac{\Gamma_i^{\min}(\sigma)}{\Gamma_i^{\min}(\sigma) - \mathbf{b}_i(\sigma)} (\Gamma_i^{\min} - \mathbf{b}_i) $$

satisfies $|\Gamma| \subset |\Gamma_i^{\min}| \setminus \{\sigma\}$ and thus $\Gamma \subseteq lex \Gamma_i^{\min}$. Also, as $\mathbf{b}_i \in \Gamma_i + \operatorname{span}(\Gamma_1, \dots, \Gamma_{i-1})$, $\Gamma_i^{\min} - \mathbf{b}_i \in \operatorname{span}(\Gamma_1, \dots, \Gamma_{i-1})$ and $\Gamma \in \Gamma_i + \operatorname{span}(\Gamma_1, \dots, \Gamma_{i-1})$. We have a contradiction with $\Gamma_i^{\min}$ as minimum of the set $\Gamma_i + \operatorname{span}(\Gamma_1, \dots, \Gamma_{i-1})$. We conclude that $\Gamma_i^{\min} = \mathbf{b}_i$. $\square$

The rest of this section links the computation of critical bases to standard matrix reduction algorithms. For simplicity, we consider chains with integer modulo 2 coefficients ($\mathbb{F} = \mathbb{Z}_2$), but these results can be extended using equivalent algorithms on matrices in *Smith normal forms* [14, Section IV.2]. Recall that the low index low($M_j$) of a non-zero column $M_j$ corresponds to the index of the lowest non-zero coefficient of the column $M_j$. Algorithm 4 is a well-known algorithm used for the computation of persistent homology [14, Section VII.1]. We also recall in Algorithm 5 the matrix algorithm presented in [10]. We denote by $(\sigma_i)_{i=1,\dots,n}$ the set of ordered k-simplices: $\sigma_1 < \dots < \sigma_n$.

**Observation 5** When considering a non-empty k-chain $\Gamma$ as a vector of $\mathbb{Z}_2^n$ written in the basis of ordered k-simplices of dimension $n$, the low index corresponds to the index of its critical simplex:

$$ \operatorname{crit}(\Gamma) = \sigma_{\operatorname{low}(\Gamma)} $$

The third property of Eq. (12) can therefore be understood as verifying that the lows of the set $(\Gamma_i)_{i=1,\dots,m}$, seen as vectors in $\mathbb{Z}_2^n$, are unique.
**Algorithm 4 Matrix reduction algorithm**

**Input:** An $n$-by-$m$ matrix $M$

for $j \leftarrow 1$ to $n$ do

while $M_j \neq 0$ and $\exists i < j$ with $\text{low}(M_i) = \text{low}(M_j)$ do

$$M_j \leftarrow M_j + M_i$$

end while

end for

**Algorithm 5 Total reduction algorithm**

**Inputs:** A vector $C$ of dimension $n$ and a reduced matrix $R$

for $i \leftarrow n$ to 1 do

if $C[i] \neq 0$ and there exists a column $R_j$ that satisfies $\text{low}(R_j) = i$ then

$$C \leftarrow \Gamma + R_j$$

end if

end for

**Observation 6** Consider a set $(\Gamma_i)_{i=1,...,m}$ basis of $\mathbb{Z}_k^{\min}(K; \mathbb{Z}_2)$ and the matrix $M$ whose columns are the corresponding vector representations in $\mathbb{Z}_2^n$ of $(\Gamma_i)_{i=1,...,m}$ in the basis of ordered $k$-simplices of dimension $n$.

* The algorithm transforming this set $(\Gamma_i)_{i=1,...,m}$ such that it satisfies the properties of Eq. (12) is the matrix reduction algorithm of $M$ (Algorithm 4), followed by a sort in increasing order along the lexicographic order on $k$-chains of the columns of $M$, resulting in a matrix $R$.

* The construction of each element $b_i$ of the critical basis as described in Lemma 15 corresponds to the total reduction algorithm (Algorithm 5) on the column $R_i$ with the submatrix of $R$ formed by the first $(i-1)$ columns.

# 8 Applications

We now explore two efficient methods of reconstruction for open surfaces in 3D using algorithms described in previous sections. The complex $K$ is assumed to be the Delaunay triangulation of the set of input points, completed into a topological 3-sphere. The lexicographic order on 2-chains is induced by the following total order on 2-simplices:

**Definition 7** For $\sigma_1, \sigma_2 \in K^{(2)}$,

$$\sigma_1 \le \sigma_2 \iff \begin{cases} R_B(\sigma_1) < R_B(\sigma_2) \\ \text{or} \\ R_B(\sigma_1) = R_B(\sigma_2) \text{ and } R_C(\sigma_1) \ge R_C(\sigma_2) \end{cases}$$

where $R_B(\sigma)$ and $R_C(\sigma)$ denote respectively the radius of the smallest enclosing ball and the radius of the circumscribed sphere of $\sigma$.
This is a specialization, for 2-simplices, of the orders previously motivated
for the characterization of Delaunay and regular triangulations in arbitrary
dimension in [11] and used in point cloud meshing applications [10].

## 8.1 Open surface reconstruction

We recall the process of open surface reconstruction, illustrated by Figure 2. We will start by assuming that we are given a 1-cycle embedded in the Delaunay triangulation. In some cases, as in Figure 8, this assumption is easy to verify, as the points of the boundary are on the convex hull of the Delaunay triangulation, and we are therefore guaranteed that the edges of this boundary are in the Delaunay triangulation. In general, guaranteeing the presence of the provided cycle in the triangulation is a challenging problem related to conforming Delaunay tetrahedralization [21–26].

The algorithm presented in Section 6 is used to compute a representative 2-chain having, as its boundary, the provided 1-cycle. As the 3-dimensional Delaunay complex has trivial 2-homology, Algorithm 2 then computes the optimal absolute chain homologous to the representative chain, which is equivalent to the optimal chain bounded by the provided 1-cycle. Different chain coefficients, namely $Z_2$ and $Q$, are interesting for open surface reconstruction. Indeed, Figure 2 shows that, when optimizing using $Z_2$ coefficients, the resulting optimal chain in $Z_2$ might not be orientable in $Q$ and therefore the two minimization problems can give different results. In applications, however, the choice of $Q$ is more appealing to obtain an oriented result. We conjecture, thanks to the unimodularity property of the boundary operator for oriented pseudomanifold [3], that optimality problems with coefficients in $Z$ can be relaxed to coefficients in $Q$. Both Algorithm 2 and Algorithm 3 of Section 6 can therefore be extended to chains with coefficients in $Z$. Figure 8 illustrates use cases of open surface reconstruction for terrains, where the boundary can be defined outside the set of points and the Delaunay triangulation is constructed on both the set of points and the points of this boundary. The observed performance for the reconstruction correlates with the quasi-linear theoretical complexity.

## 8.2 Boundary detection and critical basis

Based on the construction of a critical basis, the second process intends to automatically reconstruct open surfaces when defining the boundary, as in the previous section, would be too time-consuming. Such an example is presented in Figure 10, where the incomplete nature and presence of occlusions in the point cloud make it a difficult reconstruction problem.

To this end, we start by using a curvature estimator on the initial set of points, for instance, the Voronoi Covariance Measure (VCM) [28]. By thresholding this estimator, we can extract a subset $S$ of vertices and construct a 2-subcomplex $B$ of the Delaunay triangulation $K$, parameterized by a distance $\epsilon$, as the union of all simplices up to dimension 2 that lie inside the $\epsilon$-offset
<figure><img src="image_10.png" /><figcaption>**Fig. 8:** Example of open surface meshing on two models from the senseFly dataset [27]. Computing the optimal chains takes 1.5 and 8.0 seconds to mesh respectively 1 million (left) and 5 millions points (right). As the boundaries have been chosen outside the set of points, the triangles connected to the boundary were removed in the reconstructions.</figcaption></figure>

of $\mathcal{S}$. As we will be extracting non-trivial cycles from $B$, $\epsilon$ should be chosen according to the density of the point cloud and the size of elements we want to reconstruct.

By keeping the size of the subcomplex $B$, denoted by $p$, relatively small compared to the size $n$ of the Delaunay 3-complex, we can use traditional matrix reduction algorithm [14] to compute the reduced boundary matrix of the complex $B$ in $O(p^3)$ time complexity. After extracting a basis of $\mathbb{Z}_1(B)$ by exploring the 1-skeleton of the subcomplex, we can compute the lexicographic optimal homologous cycles for all 1-cycles of $B$, and by filtering out all zero chains, we get a set of cycles $(\gamma_i)_{i=1,...,\beta} \in \mathbb{Z}_1^{\min}(B)$ whose homology classes form a basis of $\mathcal{H}_1(B)$, with $\beta = \dim \mathcal{H}_1(B)$. As the Delaunay complex $K$ triangulates the 3-sphere $\mathbb{S}^3$, its 1- and 2-homologies are trivial. With $\rho^*$ and $\iota^*$ the homology morphisms induced respectively by the inclusion map $\rho: \mathbb{C}_2(K) \to \mathbb{C}_2(K, B)$ and the inclusion map $\iota: \mathbb{C}_1(B) \to \mathbb{C}_1(K)$, the following long exact sequence of relative homology

$$ \{0\} = \mathcal{H}_2(K) \xrightarrow{\rho^*} \mathcal{H}_2(K, B) \xrightarrow{\partial} \mathcal{H}_1(B) \xrightarrow{\iota^*} \mathcal{H}_1(K) = \{0\} $$

implies that $\mathcal{H}_2(K, B) \xrightarrow{\partial} \mathcal{H}_1(B)$ is an isomorphism. By finding representative chains in $\mathbb{Z}_2(K, B)$ (using the algorithm presented in Section 6) for each element of $(\gamma_i)_{i=1,...,\beta}$, we get a set of cycles whose homology classes form a basis of $\mathcal{H}_2(K, B)$. Using Algorithm 2, we then find the lexicographic optimal relative cycle homologous to each representative chain and construct a basis $(\Gamma_i)_{i=1,...,\beta}$ of $\mathbb{Z}_2^{\min}(K, B)$. Finally, following Observation 6, the critical
<figure><img src="image_11.png" /><figcaption>**Fig. 9:** An illustration of the steps in the proposed method. The red edge represents the edge with the highest weight in the complex B.</figcaption></figure>

basis can be obtained from any basis of $Z_2^{\min}(K, B)$ using matrix reduction algorithms. This construction has a $O(\beta^2n)$ time complexity.

The whole process, excluding the complexity of computing the Delaunay triangulation and calling the feature estimator, has a $O(p^3 + \beta n \log n + \beta^2 n)$ time complexity, where $n$ is the size of the complex $K$, $p$ the size of the subcomplex $B$, $\beta$ the dimension of 1-homology of $B$ (or equivalently the 2-homology of $(K, B)$). In our experiments, the size of the complex $B$, constructed from the VCM estimation, was fortunately small enough to make the cubic-time component of the method feasible.

We emphasize that constructing the critical basis produces significantly better results than simply returning the basis $(\Gamma_i)_{i=1,...,\beta}$ of $Z_2^{\min}(K, B)$. This improvement largely stems from the fact that, unlike $(\Gamma_i)_{i=1,...,\beta}$, the critical basis does not depend on a specific choice of basis for $Z_1^{\min}(B)$. As illustrated in Figure 9, the supports of the elements $(\Gamma_i)_{i=1,...,\beta}$ of $Z_2^{\min}(K, B)$ often overlap, since their construction is tightly coupled with the chosen basis for $Z_1^{\min}(B)$. In contrast, while we cannot guarantee that the supports of the critical basis elements are entirely disjoint, they exhibit far less overlap in our experiments. Viewed as sets of triangles, the elements of the critical basis not only provides a full reconstruction of the scene but also yields a canonical and meaningful geometric decomposition. This structure allows for instance to selectively fill or keep holes corresponding to occluded regions in the input point cloud, by removing some of the largest elements of this critical basis, as demonstrated in Figure 10d.

We believe that many other interesting applications can be further developed from the algorithms presented in this work. For instance, the ability to enforce a given boundary can be useful for meshing large sets of points, by
<figure><img src="image_12.png" /><figcaption>(a) Sharp feature estimation</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(b) Cycle basis of $Z_1^{\min}(B)$</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(c) Critical basis of $Z_2^{\min}(K, B)$</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>(d) Removing the first few chains</figcaption></figure>

**Fig. 10:** After choosing a threshold for the sharp feature estimation (a) and constructing an offset complex $B$, the basis of $Z_1^{\min}(B)$ forms a “wireframe” representation of the scene (b). The critical basis correctly reconstructs most parts of the scene (c). In this basis, the largest elements often correspond to the perceived holes of the original set of points (d).

implementing a tiling strategy and guaranteeing that each tile mesh coincides with other neighboring tiles. Also, the process described in this section using critical bases could allow reconstructing stratified objects, given a subcomplex $B$ that correctly captures the singular edges of the object.

**Acknowledgments.** This work has benefited from many discussions and exchanges on related topics with Dominique Attali, Jean-Daniel Boissonnat and Mathijs Wintraecken.

**Conflict of interests.** On behalf of all authors, the corresponding author states that there is no conflict of interest.
# Appendix A Crash course on simplicial homology

## A.1 Simplices and complexes

An (abstract) simplicial complex $K$ is a collection of finite non-empty sets that is closed under taking subsets, i.e. every subset of an element of $K$ is also in $K$. A $k$-simplex of $K$ is an element of $K$ of size $k+1$. We denote by $K^{(k)}$ the set of $k$-simplices in $K$.

A simplex $\tau$ subset of $\sigma$ is called a **face** of $\sigma$, and is denoted as $\tau \preceq \sigma$. Reversely, we say $\sigma$ a **coface** of $\tau$.

A subcomplex $B$ of a simplicial complex $K$ is a simplicial complex whose simplices are included in $K$. In particular, the **$k$-skeleton** of $K$, containing all simplices in $K$ of dimension at most $k$, is a subcomplex of $K$.

## A.2 Absolute homology

Let $K$ be a simplicial complex of dimension at least $k$. While the notions of chains and homology can be defined with coefficients in any ring, we consider here coefficients in a field $\mathbb{F}$, where we have in mind, in particular, the cases of the field of integers modulo 2 ($\mathbb{F} = \mathbb{Z}_2$) and the field of rationals ($\mathbb{F} = \mathbb{Q}$). A **$k$-chain** $A$ with coefficients in $\mathbb{F}$ is a formal sum of $k$-simplices:

$$A = \sum_{i} x_{i} \sigma_{i}, \text{ with } x_{i} \in \mathbb{F} \text{ and } \sigma_{i} \in K^{(k)}$$

We denote by $C_k(K)$, or $C_k(K; \mathbb{F})$ when we want to emphasize the chain coefficient, the vector space of $k$-chains in the complex $K$.

For a chain $\Gamma \in C_k(K)$, its **support**, denoted $|\Gamma|$, is the set of simplices for which the coefficient in $\Gamma$ is not zero:

$$|\Gamma| = \{ \sigma \in K^{(k)}, \Gamma(\sigma) \neq 0 \}$$

When $\mathbb{F} = \mathbb{Z}_2$, the chain coefficient in front of any simplex can be interpreted as indicating the existence of this simplex in the chain. We can view $k$-chains as sets of $k$-simplices: for a $k$-simplex $\sigma$ and a $k$-chain $A$, we then write that $\sigma \in A$ if the coefficient for $\sigma$ in $A$ is 1. With this convention, the sum (or difference) of two chains corresponds to the symmetric difference on their sets. In what follows, a $k$-simplex $\sigma$ can also be interpreted as the $k$-chain containing only the $k$-simplex $\sigma$.

The **boundary operator** $\partial_k : C_k(K) \to C_{k-1}(K)$ is the linear map defined for any $k$-simplex $\sigma = [a_0, \dots, a_k]$ as:

$$\partial_k \sigma = \sum_{i=0}^{k} (-1)^i [a_0, \dots, \hat{a}_i, \dots, a_k]$$
where the symbol $\hat{a}_i$ means the vertex $a_i$ is deleted from the array. The kernels and images of the boundary operator form respectively the vector space of cycles and boundaries:

$$ \mathbf{Z}_k(K) =_{\text{def.}} \text{Ker} \partial_k = \{ \Gamma \in \mathbf{C}_k(K), \partial_k \Gamma = 0 \} $$

$$ \mathbf{B}_k(K) =_{\text{def.}} \text{Im} \partial_{k+1} = \{ \Gamma \in \mathbf{C}_k(K), \exists A \in \mathbf{C}_{k+1}(K) | \Gamma = \partial_{k+1} A \} $$

The following fundamental property of the boundary operator $\partial_k \partial_{k+1} = 0$ implies that $\text{Im} \partial_{k+1} \subset \text{Ker} \partial_k$, or equivalently $\mathbf{B}_k(K) \subset \mathbf{Z}_k(K)$.

**Homology groups** – forming vector spaces over the field $\mathbb{F}$ – are defined as quotient spaces of cycles over boundaries:

$$ \mathcal{H}_k(K) =_{\text{def.}} \frac{\mathbf{Z}_k(K)}{\mathbf{B}_k(K)} $$

Two $k$-cycles $A, A' \in \mathbf{Z}_k(K)$ are then said to be **homologous** if they belong to the same homology class in $\mathcal{H}_k(K)$, or equivalently if $A - A' = \partial_{k+1} B$ for some $(k+1)$-chain $B$. By extension, we also say two $k$-chains $\Gamma, \Gamma' \in \mathbf{C}_k(K)$ are homologous if their difference is a boundary, i.e. there exists a $(k+1)$-chain $B$ such that $\Gamma - \Gamma' = \partial B$.

### A.3 Relative homology

Roughly speaking, the relative homology of a simplicial pair $(K, B)$ is constructed similarly to absolute homology but "ignores" all the part of $K$ inside $B$. Given a simplicial subcomplex $B$ of $K$, relative $k$-chains are defined as classes in the following quotient space:

$$ \mathbf{C}_k(K, B) =_{\text{def.}} \frac{\mathbf{C}_k(K)}{\mathbf{C}_k(B)} $$

Denote by $\partial_k^{(r)}$ the relative $k$-boundary operator in $(K, B)$ and by $\partial_k^{(a)}$ the absolute $k$-boundary operator in $K$. For any absolute $k$-chain $\Gamma \in \mathbf{C}_k(K)$,

$$ \partial_k^{(r)}(\Gamma + \mathbf{C}_k(B)) =_{\text{def.}} \partial_k^{(a)}(\Gamma) + \mathbf{C}_{k-1}(B) $$

This is well-defined as $\partial_k^{(a)}(\mathbf{C}_k(B)) \subseteq \mathbf{C}_{k-1}(B)$. Relative cycles and boundaries, are still defined as respective kernel and image of the relative boundary operator:

$$ \mathbf{Z}_k(K, B) =_{\text{def.}} \text{Ker} \partial_k^{(r)} $$

$$ \mathbf{B}_k(K, B) =_{\text{def.}} \text{Im} \partial_{k+1}^{(r)} $$
Translated in terms of absolute chains, for $\Gamma \in \mathbf{C}_k(K)$,

$$ \Gamma + \mathbf{C}_k(B) \in \mathbf{Z}_k(K, B) \iff |\partial_k^{(a)} \Gamma| \subset B $$

$$ \Gamma + \mathbf{C}_k(B) \in \mathbf{B}_k(K, B) \iff \exists A \in \mathbf{C}_{k+1}(K), |\Gamma - \partial_{k+1}^{(a)} A| \subset B $$

Relative homology is again defined as the quotient space of relative cycles over relative boundaries:

$$ \mathcal{H}_k(K, B) = \underset{\text{def.}}{\frac{\mathbf{Z}_k(K, B)}{\mathbf{B}_k(K, B)}} $$

While, strictly speaking, a relative k-chain $\Gamma \in \mathbf{C}_k(K, B)$ is a class, we allow ourselves to write, for simplicity,

$$ \Gamma = \sum_{\sigma_i \in K \setminus B} x_i \sigma_i $$

where the simplex $\sigma_i \in K \setminus B$ stands in this case for $\sigma_i + \mathbf{C}_k(B)$. For all that follows, the distinction between absolute and relative boundary operators will be omitted and the notation $\partial_k$ will denote either the absolute and relative boundary operator depending on the context.
# Appendix B Subroutine complexities for Algorithm 3

We recall that, for simplicity, the algorithms described in this section assume the chain coefficient is $\mathbb{F} = \mathbb{Z}_2$, but the approach extends similarly to an arbitrary coefficient field. This would require to take care of the signs of chains, in particular, in Algorithm 6, some + signs should be replaced by - signs.

## B.1 GetHighestVertex and GetAdjacentVertices

Thanks to Condition 1, each edge in the chain A can be represented by the ordered pair of vertices $(v_1, v_2)$ such that $z(v_1) > z(v_2)$, one can define the following total order on the edges of A:

$$ (v_1, v_2) \le (v'_1, v'_2) \iff_{\text{def.}} \begin{cases} z(v_1) > z(v'_1) \\ \text{or } v_1 = v'_1 \text{ and } z(v_2) \ge z(v'_2) \end{cases} $$

This order on the edges of A being maintained through the update of A, the procedure **GetHighestVertex(A)** merely returns the first vertex of the first edge in the ordered list. The procedure **GetAdjacentVertices(a, A)** traverses the ordered list from the beginning as long as the first vertex of edges remains the same - the one returned by **GetHighestVertex(A)** - and returns the list of corresponding second vertices.

The initial ordering of the edges in A can be performed at a cost $O(n \log n)$. Each update of this ordering, when an edge is added or removed from A, can be done at a cost $O(\log n)$.

During Algorithm 3, each edge e added to A is associated to a triangle $a \lor e$, which is only explored once as the highest vertex a itself will not be visited again. This implies that the number of updates is $O(n)$, which gives a total cost of $O(n \log n)$.

## B.2 GetLowerLink

Thanks to Condition 1, each triangle in $Del(P)$ can be represented by the ordered triple of vertices $(v_1, v_2, v_3)$ such that $z(v_1) > z(v_2) > z(v_3)$ and one can define the following total order on the triangles of $Del(P)$:

$$ (v_1, v_2, v_3) \le (v'_1, v'_2, v'_3) \iff_{\text{def.}} \begin{cases} z(v_1) > z(v'_1) \\ \text{or } v_1 = v'_1 \text{ and } z(v_2) > z(v'_2) \\ \text{or } v_1 = v'_1 \text{ and } v_2 = v'_2 \text{ and } z(v_3) \ge z(v'_3) \end{cases} $$

Observe that, in Algorithm 3, the z coordinate of the current highest vertex a is decreasing along the main loop. The procedure **GetLowerLink(a, Del(P))** iterates along the above total order on triangles represented as vertex triples, until the first vertex of the ordered triple is equal to a, all the triangles in
the lower star of a appear then contiguously in the list, as long as the first vertex remains a. The lower link of a is then given by the set of edges corresponding to the last two vertices of each such triples. We see that all calls to **GetLowerLink**(a, Del(P)) correspond to a single pass through the ordered triples. It results that the overall cost is dominated by the $O(n \log n)$ of the preprocessing sort.

## B.3 GetEdgesConnecting

The subroutine **GetEdgesConnecting**(V_a, LL) requires a bit more attention to obtain the correct complexity. Denote by m the size of the lower link LL of a vertex a. The most obvious way of implementing this subroutine is by creating a spanning tree T of the lower link graph (using a breadth-first search for instance), which has a $O(m)$ time complexity. From this spanning tree, we could partition the even set of vertices V_a into pairs and construct a path in T for each of these pairs. However, if V_a contains $2k = O(m)$ vertices, this leads to computing k paths in the spanning tree, which has a $O(m^2)$ time complexity, followed by adding up to km edges in A, which has an $O(m^2 \log n)$ time complexity.

Instead, we describe Algorithm 6. When creating this spanning tree T of the 1-skeleton LL of the lower link of a vertex a, we also assign an integer rank to each vertex such that the root has rank 0 and each non-root vertex has a rank higher than its parent.

A spanning tree on LL can be computed in time $O(m)$ where m is the size of LL. A list indexing the vertices ordered by rank can be built along the tree construction at the same $O(m)$ cost, since, when building the spanning tree, the vertices are added to the resulting tree along this same order.

**Algorithm 6 GetEdgesConnecting**

**Input:** An even set of vertices $V_a$ in the lower link of a vertex a and a spanning tree T of the 1-skeleton LL of this lower link
**Output:** A set of edges E in T such that $\partial E = V_a$
$E \leftarrow \emptyset$
$V \leftarrow V_a$
**for** $rank \leftarrow m - 1, 1$ **do**
$V \leftarrow VERTEX(rank)$
**if** $v \in V$ **then**
$p \leftarrow GETPARENTINTREE(v, T)$
$V \leftarrow V + v + p$
$E \leftarrow E + v \lor p$
**end if**
**end for**
**Lemma 16** After creating, as a $O(m)$ preprocessing, a spanning tree with $m' < m$ vertices together with a list indexing the vertices ordered by rank, Algorithm 6 allows an implementation of the procedure **GetEdgesConnecting**($V_a, LL$) at a cost of $O(m')$, where $m'$ is the size of the tree.

*Proof* The correctness follows from the preservation of the following property along the algorithm:

$$ \partial E = V_a + V \qquad (B1) $$

The algorithm iterates on the rank, from $m' - 1$ to 1. When the rank is $i$, if the corresponding vertex belongs to $V$ it is then removed from $V$. It follows that, at the end of step $i$, $V$ cannot contain any vertex of rank greater or equal to $i$. At the end of the iteration corresponding to rank 1, $V$ is therefore a subset of $\{v_0\}$, where $v_0$ is the root vertex with rank 0. As $V$ is a 0-boundary, it contains an even number of vertices, therefore $V$ has to be the empty set. Invariant (B1) then gives $\partial E = V_a$ as required.

If an array of size $m$ contains all vertices indexed by their rank, each call to the procedure **Vertex(rank)** costs $O(1)$. If the evolving set of vertex $V$ is represented by an array of booleans of size $m$, where entry $k$ indicates the membership to $V$ of the vertex with rank $k$, the membership predicate $v \in V$ costs $O(1)$. When $V$ is updated, updating this membership array can be done also in time $O(1)$. It follows that each line in the algorithm costs $O(1)$. For this reason, the cost of Algorithm 6 is $O(m)$. $\square$
References

[1] Chen, C., Freedman, D.: Hardness Results for Homology Localization. Discrete & Computational Geometry 45(3), 425–448 (2011). https://doi.org/10.1007/s00454-010-9322-8

[2] Borradaile, G., Maxwell, W., Nayyeri, A.: Minimum bounded chains and minimum homologous chains in embedded simplicial complexes. In: Cabello, S., Chen, D.Z. (eds.) 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 164, pp. 21–12115. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020). https://doi.org/10.4230/LIPIcs.SoCG.2020.21

[3] Dey, T.K., Hirani, A.N., Krishnamoorthy, B.: Optimal Homologous Cycles, Total Unimodularity, and Linear Programming. SIAM Journal on Computing 40(4), 1026–1044 (2011). https://doi.org/10.1137/100800245

[4] Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’05, pp. 1038–1046. Society for Industrial and Applied Mathematics, USA (2005)

[5] Busaryev, O., Cabello, S., Chen, C., Dey, T.K., Wang, Y.: Annotating Simplices with a Homology Basis and Its Applications. In: Fomin, F.V., Kaski, P. (eds.) Algorithm Theory – SWAT 2012, pp. 189–200. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)

[6] Dey, T.K., Li, T., Wang, Y.: Efficient algorithms for computing a minimal homology basis. arXiv:1801.06759 [cs, math] (2018) arXiv:1801.06759 [cs, math]

[7] Sullivan, J.M.: A Crystalline Approximation Theorem for Hypersurfaces. PhD Thesis, Princeton Univ. (October 1990)

[8] Chambers, E.W., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In: Proceedings of the 25th Annual Symposium on Computational Geometry - SCG ’09, p. 377. ACM Press, Aarhus, Denmark (2009). https://doi.org/10.1145/1542362.1542426

[9] Dey, T.K., Hou, T., Mandal, S.: Computing minimal persistent cycles: Polynomial and hard cases. In: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’20, pp. 2587–2606. Society for Industrial and Applied Mathematics, USA (2020)

[10] Cohen-Steiner, D., Lieutier, A., Vuillamy, J.: Lexicographic optimal
homologous chains and applications to point cloud triangulations. Discrete & Computational Geometry **68**(4), 1155–1174 (2022)

[11] Cohen-Steiner, D., Lieutier, A., Vuillamy, J.: Delaunay and regular triangulations as lexicographic optimal chains. Discrete & Computational Geometry, 1–50 (2023)

[12] Orlin, J.B.: Max flows in O(nm) time, or better. In: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing - STOC '13, p. 765. ACM Press, Palo Alto, California, USA (2013). https://doi.org/10.1145/2488608.2488705

[13] Munkres, J.R.: Elements of Algebraic Topology, 1st edn. CRC Press, ??? (2018). https://doi.org/10.1201/9780429493911

[14] Edelsbrunner, H., Harer, J.: Computational Topology: An Introduction. American Mathematical Society, Providence, R.I (2010)

[15] Galler, B.A., Fisher, M.J.: An improved equivalence algorithm. Communications of the ACM **7**(5), 301–303 (1964). https://doi.org/10.1145/364099.364331

[16] Tarjan, R.E., van Leeuwen, J.: Worst-case Analysis of Set Union Algorithms. Journal of the ACM **31**(2), 245–281 (1984). https://doi.org/10.1145/62.2160

[17] Edelsbrunner, H., Mücke, E.P.: Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics **9**(1), 66–104 (1990). https://doi.org/10.1145/77635.77639

[18] Edelsbrunner, H., Ölsböck, K.: Tri-partitions and bases of an ordered complex **64**(3), 759–775. https://doi.org/10.1007/s00454-020-00188-x. Accessed 2023-12-20

[19] Edelsbrunner, H., Zomorodian, A.: Computing linking numbers of a filtration **5**(2), 19–37. Publisher: International Press of Boston. Accessed 2023-12-20

[20] Zomorodian, A., Carlsson, G.: Computing persistent homology **33**(2), 249–274. https://doi.org/10.1007/s00454-004-1146-y. Accessed 2023-12-20

[21] Cohen-Steiner, D., Colin de Verdière, É., Yvinec, M.: Conforming Delaunay triangulations in 3D. Computational Geometry **28**(2-3), 217–233 (2004). https://doi.org/10.1016/j.comgeo.2004.03.001

[22] Ruppert, J.: A Delaunay Refinement Algorithm for Quality 2-Dimensional
Mesh Generation. Journal of Algorithms **18**(3), 548–585 (1995). https://doi.org/10.1006/jagm.1995.1021

[23] Si, H.: TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator. ACM Transactions on Mathematical Software **41**(2), 1–36 (2015). https://doi.org/10.1145/2629697

[24] Si, H.: Adaptive tetrahedral mesh generation by constrained Delaunay refinement. International Journal for Numerical Methods in Engineering **75**(7), 856–880 (2008). https://doi.org/10.1002/nme.2318

[25] Murphy, M., Mount, D.M., Gable, C.W.: A point-placement strategy for conforming Delaunay tetrahedralization. International Journal of Computational Geometry & Applications **11**(06), 669–682 (2001). https://doi.org/10.1142/S0218195901000699

[26] Shewchuk, J.R.: Tetrahedral mesh generation by Delaunay refinement. In: Proceedings of the Fourteenth Annual Symposium on Computational Geometry - SCG '98, pp. 86–95. ACM Press, Minneapolis, Minnesota, United States (1998). https://doi.org/10.1145/276884.276894

[27] Sensefly: Example Dataset for Mapping. https://www.sensefly.com/education/datasets/ (2011)

[28] Mérigot, Q., Ovsjanikov, M., Guibas, L.J.: Voronoi-Based Curvature and Feature Estimation from Point Clouds. IEEE Transactions on Visualization and Computer Graphics **17**(6), 743–756 (2011). https://doi.org/10.1109/TVCG.2010.261