惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

爱范儿
爱范儿
Y
Y Combinator Blog
博客园 - Franky
D
Docker
B
Blog RSS Feed
M
MIT News - Artificial intelligence
雷峰网
雷峰网
博客园 - 司徒正美
人人都是产品经理
人人都是产品经理
宝玉的分享
宝玉的分享
S
SegmentFault 最新的问题
GbyAI
GbyAI
Recent Announcements
Recent Announcements
Martin Fowler
Martin Fowler
H
Hackread – Cybersecurity News, Data Breaches, AI and More
MyScale Blog
MyScale Blog
B
Blog
H
Help Net Security
Microsoft Security Blog
Microsoft Security Blog
WordPress大学
WordPress大学
Vercel News
Vercel News
The Cloudflare Blog
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
Google DeepMind News
Google DeepMind News

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
An Algorithm for Fast and Correct Computation of Reeb Spa...
Amit Chattopadhyay, Yashwanth Ramamurthi, Osamu Saeki · 2024-03-11 · via cs.DS updates on arXiv.org

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. 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}$ 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)$, where $n$ is the total number of simplices in $\mathbb{M}$, $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$ is the upper bound on the number of simplices in the link of an edge of $\mathbb{M}$.