<p>The Reeb space is a fundamental data structure in computational topology that represents the fiber topology of a multi-field (or multiple scalar fields), extending the level set topology of a scalar field. For piecewise-linear (PL) bivariate fields, the Reeb spaces are 2-dimensional polyhedrons while for PL scalar fields, the Reeb graphs (or Reeb spaces) are of dimension 1. Efficient algorithms have been designed for computing Reeb graphs, however, computing correct Reeb spaces for PL bivariate fields is a challenging open problem. There are only a few implementable algorithms in the literature for computing Reeb space or its approximation, via range quantization or by computing a Jacobi fiber surface, which are computationally expensive or have correctness issues, i.e., the computed Reeb space may not be topologically equivalent or homeomorphic to the actual Reeb space. In the current paper, we propose a novel algorithm for fast and correct computation of the Reeb space corresponding to a generic PL bivariate field defined on a triangulation <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathbb {M}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">M</mi> </math></EquationSource> </InlineEquation> of a 3-manifold without boundary, leveraging the fast algorithms for computing Reeb graphs in the literature. Our algorithm is based on the computation of a Multi-Dimensional Reeb Graph (MDRG) which is first proved to be homeomorphic with the Reeb space. For the correct computation of the MDRG, we compute the Jacobi set of the PL bivariate field and its projection into the Reeb space, called the Jacobi structure. Finally, the correct Reeb space is obtained by computing a net-like structure embedded in the Reeb space and then computing its 2-sheets in the net-like structure. The time complexity of our algorithm is <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {O}(n^2 + n\, c_{int}\, \log n + nc_L^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>+</mo> <mi>n</mi> <mspace width="0.166667em" /> <msub> <mi>c</mi> <mrow> <mi mathvariant="italic">int</mi> </mrow> </msub> <mspace width="0.166667em" /> <mo>log</mo> <mi>n</mi> <mo>+</mo> <mi>n</mi> <msubsup> <mi>c</mi> <mi>L</mi> <mn>2</mn> </msubsup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <i>n</i> is the total number of simplices in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathbb {M}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">M</mi> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$c_{int}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>c</mi> <mrow> <mi mathvariant="italic">int</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> is the number of intersection points of the projections of the non-adjacent Jacobi set edges on the range of the bivariate field, and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$c_L$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>c</mi> <mi>L</mi> </msub> </math></EquationSource> </InlineEquation> is the upper bound on the number of simplices in the link of an edge of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathbb {M}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">M</mi> </math></EquationSource> </InlineEquation>. This complexity is comparable with the fastest algorithm available in the literature. Moreover, we claim to provide the first algorithm to compute the topologically correct Reeb space without using range quantization.</p>

An algorithm for fast and correct computation of Reeb spaces for PL bivariate fields

期刊论文
出版模式：

开放获取
发表日期：

2026年7月11日

查看全文

Amit Chattopadhyay,
Yashwanth Ramamurthi,
Osamu Saeki

摘要

The Reeb space is a fundamental data structure in computational topology that represents the fiber topology of a multi-field (or multiple scalar fields), extending the level set topology of a scalar field. For piecewise-linear (PL) bivariate fields, the Reeb spaces are 2-dimensional polyhedrons while for PL scalar fields, the Reeb graphs (or Reeb spaces) are of dimension 1. Efficient algorithms have been designed for computing Reeb graphs, however, computing correct Reeb spaces for PL bivariate fields is a challenging open problem. There are only a few implementable algorithms in the literature for computing Reeb space or its approximation, via range quantization or by computing a Jacobi fiber surface, which are computationally expensive or have correctness issues, i.e., the computed Reeb space may not be topologically equivalent or homeomorphic to the actual Reeb space. In the current paper, we propose a novel algorithm for fast and correct computation of the Reeb space corresponding to a generic PL bivariate field defined on a triangulation $\mathbb {M}$ $M$ of a 3-manifold without boundary, leveraging the fast algorithms for computing Reeb graphs in the literature. Our algorithm is based on the computation of a Multi-Dimensional Reeb Graph (MDRG) which is first proved to be homeomorphic with the Reeb space. For the correct computation of the MDRG, we compute the Jacobi set of the PL bivariate field and its projection into the Reeb space, called the Jacobi structure. Finally, the correct Reeb space is obtained by computing a net-like structure embedded in the Reeb space and then computing its 2-sheets in the net-like structure. The time complexity of our algorithm is $\mathcal {O}(n^2 + n\, c_{int}\, \log n + nc_L^2)$ $O (n^{2} + n c_{int} log n + n c_{L}^{2})$ , where n is the total number of simplices in $\mathbb {M}$ $M$ , $c_{int}$ $c_{int}$ is the number of intersection points of the projections of the non-adjacent Jacobi set edges on the range of the bivariate field, and $c_L$ $c_{L}$ is the upper bound on the number of simplices in the link of an edge of $\mathbb {M}$ $M$ . This complexity is comparable with the fastest algorithm available in the literature. Moreover, we claim to provide the first algorithm to compute the topologically correct Reeb space without using range quantization.