The Medial Axis Transform (MAT) is a complete shape descriptor capable of reconstructing the geometry of the original domain. A high-quality MAT should not only facilitate high-fidelity reconstruction but also capture structural features—for instance, by aligning the MAT boundary with the locus of rolling ball centers within fillet regions. However, computing such an ideal MAT remains a significant challenge, particularly when the input is a discrete triangle mesh. In this paper, we follow the established technical pipeline of initializing the MAT via a 3D Voronoi diagram of surface samples and subsequently simplifying the Voronoi structure through a QEM-like scheme. Our key insight is to explicitly track the correspondence between MAT vertices and surface regions throughout the progressive simplification process, ensuring that the resulting MAT triangles accurately reflect the intrinsic symmetries between surface patches. We translate these geometric requirements into a suite of priority control strategies that govern the sequencing of edge collapses. Through extensive evaluation against state-of-the-art MAT algorithms, we validate the strong performance of our approach regarding runtime efficiency, structural alignment, boundary regularity, triangle quality, and robustness to noise. Our resulting MATs remain highly expressive for both articulated shapes and CAD models, even under extreme simplification—effectively capturing the global structure of complex geometries with only a few hundred vertices. Finally, we showcase the utility of our approach through two potential applications: capturing the locus of rolling ball centers within fillet regions, a structural capability not previously demonstrated in the existing literature, and surface extraction from unsigned distance fields, where the medial axis of the є-isosurface naturally yields a clean single-layer result. Source code is available at https://github.com/sssomeone/structural-mat.
论文检索
输入标题、作者或关键词，从 1,090 篇学术成果中精准定位
We introduce a spatially discrete formulation of the Schrödinger bridge problem on meshes and grids that enables structure-preserving and scalable interpolation between probability distributions. Our approach builds on the duality between entropy-regularized optimal transport and the log-heat equation, deriving a discrete theory that is compatible with mesh-based finite element discretizations. The resulting Sinkhorn algorithm alternates application of the heat kernel with multiplicative updates to enforce marginal constraints. Compared to interpolation via Wasserstein barycenters, our formulation produces sharper interpolants for a given level of regularization and enforces exact endpoint marginals, in addition to enjoying faster computation. It also scales to high-resolution meshes and finer temporal discretizations, avoiding the prohibitive cost of directly discretizing dynamical transport. We demonstrate our approach across mesh- and grid-based applications, including displacement interpolation, shape interpolation, and color histogram manipulation, highlighting its ability to achieve geometric fidelity with computational efficiency.
Computing the Hausdorff distance between triangle meshes with guaranteed accuracy is a computationally intensive task. Conventional Branch-and-Bound (B&B) approaches are fundamentally ill-suited for massive parallelism. Their reliance on a global priority queue (PQ) for both best-first scheduling and global termination checks creates a serial bottleneck that prevents scalable performance. We introduce PQ-Free HD, a parallel B&B framework that eliminates this dependency by decoupling the algorithm's termination logic from its scheduling order. This is achieved by relaxing the culling criterion, thereby replacing the priority queue with a contention-free ring buffer, which transforms the execution model from a state-dependent serial search into a high-throughput, asynchronous batch-processing paradigm. The framework consists of four key components: (1) a parallel priority-queue-free B&B paradigm; (2) a hierarchical GPU execution architecture combining batched depth-first scheduling with fused collaborative kernels; (3) a geometrically robust seven-stage culling pipeline featuring novel tests for challenging geometries; and (4) a compact 29-byte procedural task descriptor that achieves an 83.9% memory reduction. Evaluations demonstrate substantial speedups: a median of 71.7× over the state-of-the-art CPU algorithm on general benchmarks, and exceeding 10,000× on challenging CAD models with dense planar structures. The throughput advantage scales super-linearly with problem complexity. We showcase practical value by building a strictly Hausdorff-distance-bounded mesh simplification tool entirely on the GPU. Our work provides a new method for high-throughput, tolerance-controllable B&B-based geometric queries on GPUs. Code and data are available at https://github.com/huzhihao2001/pqfree-hd.
Signed Distance Fields (SDFs) are a powerful volumetric representation for 3D geometry. Recent advances in surface generation from SDFs increasingly rely on learnable surface representations and direct mesh supervision. In this work, we challenge this trend and show that high-quality surface reconstruction can be achieved by learning to refine the volumetric signal itself. We present SuperSDF, a learning-based approach for sparse SDF super-resolution that operates directly in SDF space, without auxiliary surface representations or mesh-level supervision. Using a sparse voxel neural network restricted to a narrow band near the surface, our method predicts high-resolution signed-distance values from coarse inputs in a scalable and resolution-agnostic manner. Standard isosurface extraction algorithms can then process the resulting super-resolved SDFs to produce accurate, detailed surface meshes. Our results show that learning-based SDF upsampling alone is sufficient to recover fine geometric details missed by classical interpolation and prior reconstruction methods. Compared to state-of-the-art machine learning approaches, our method generates higher-fidelity surfaces at a fraction of the computational cost and scales to volumetric resolutions that were previously impractical.
Voronoi diagrams, and their more general weighted counterpart, power diagrams, are fundamental geometric constructs with wide-ranging applications in biology, physics simulation, and computer graphics. Recently, they have gained renewed attention in mesh-based neural rendering. Despite being extensively studied, the construction of 3D Voronoi diagrams for large-scale point sets remains computationally expensive, limiting their adoption in large-scale applications. Existing CPU-based approaches typically rely on computing its dual, the Delaunay tetrahedralization, but are prohibitively slow for large diagrams, while GPU-based methods either struggle to scale efficiently to large point sets or assume homogeneous point distributions. The weighted case, power diagrams, is even less explored in this context. Existing approaches are typically tailored to the application at hand, assuming homogeneous point distributions and small weight variations, making them unsuitable for general use in more complex heterogeneous data. In this paper, we present a highly parallelizable GPU algorithm for the fast construction of large-scale 3D Voronoi and power diagrams. Our approach constructs each convex cell from a weighted 3D point by progressively clipping an initial cell volume against bisecting planes induced by candidate neighboring points. To efficiently identify candidate neighbors under arbitrary spatial distributions, we introduce a culling criterion based on directional geometric bounds of the evolving cell, combined with a hierarchical best-first traversal of bounding volumes. We achieve performance on par with state-of-the-art Delaunay tetrahedralization methods on small and moderate problem sizes, while exhibiting robust scalability to large point sets and diverse spatial distributions. Moreover, our method naturally generalizes to power diagrams without additional assumptions. To facilitate reproducibility and future research, we release our source code, see https://research.zenseact.com/publications/paragram.
As the Web transitions from static retrieval to generative interaction, the escalating environmental footprint of Large Language Models (LLMs) presents a critical sustainability challenge. Current paradigms indiscriminately apply computation-intensive strategies like Chain-of-Thought (CoT) to billions of daily queries, causing LLM overthinking, a redundancy that amplifies carbon emissions and operational barriers. This inefficiency directly undermines UN Sustainable Development Goals 13 (Climate Action) and 10 (Reduced Inequalities) by hindering equitable AI access in resource-constrained regions. To address this, we introduce EcoThink, an energy-aware adaptive inference framework designed to reconcile high-performance AI intelligence with environmental responsibility. EcoThink employs a lightweight, distillation-based router to dynamically assess query complexity, skipping unnecessary reasoning for factoid retrieval while reserving deep computation for complex logic. Extensive evaluations across 9 diverse benchmarks demonstrate that EcoThink reduces inference energy by 40.4% on average (up to 81.9% for web knowledge retrieval) without statistically significant performance loss. By mitigating algorithmic waste, EcoThink offers a scalable path toward a sustainable, inclusive, and energy-efficient generative AI Agent.
Online financial systems for stock prediction, portfolio optimization, and algorithmic trading must remain robust against rare and volatile market events, but historical data often fails to capture diverse unprecedented financial risks, creating a major bottleneck for systematic stress testing. To address this, we propose Financial Wind Tunnel (FWT), a deployable, retrieval-augmented market simulator that generates realistic, controllable, and adaptable financial dynamics for industrial-scale training and testing. FWT integrates both macro- and micro-level market patterns through a retrieval mechanism that conditions diffusion on relevant trends, supporting real-time and interpretable generation. Unlike existing methods that lack transferability across markets and scales, FWT supports large-scale cross-market pattern synthesis and what-if causal generation, enabling generalizable simulation beyond local historical regimes. We further introduce a simulation-driven optimizer for downstream models, enabling continuous improvement of online quantitative strategies. Deployed in production pipelines on CSI300 and HKSE components, FWT demonstrates measurable gains in stock prediction and portfolio optimization performance while maintaining scalability and operational reliability, offering a practical system for quantitative finance and stress testing.
The rise of Internet of Vehicles (IoV) technologies is transforming traffic management from isolated control to a collective, multi-vehicle process. At the heart of this shift is multi-vehicle dynamic navigation, which requires simultaneously routing large fleets under evolving traffic conditions. Existing path search algorithms and reinforcement learning methods struggle to scale to city-wide networks, often failing to capture the nonlinear, stochastic, and coupled dynamics of urban traffic. To address these challenges, we propose CityNav, a hierarchical, LLM-powered framework for large-scale multi-vehicle navigation. CityNav integrates a global traffic allocation agent, which coordinates strategic traffic flow distribution across regions, with local navigation agents that generate locally adaptive routes aligned with global directives. To enable effective cooperation, we introduce a cooperative reasoning optimization mechanism, in which agents are jointly trained with a dual-reward structure: individual rewards promote per-vehicle efficiency, while shared rewards encourage network-wide coordination and congestion reduction. Extensive experiments on four real-world road networks of varying scales (up to 1.6 million roads and 430,000 intersections) and traffic datasets demonstrate that CityNav consistently outperforms nine classical path search and RL-based baselines in city-scale travel efficiency and congestion mitigation. Our results highlight the potential of LLMs to enable scalable, adaptive, and cooperative city-wide traffic navigation, providing a foundation for intelligent, large-scale vehicle routing in complex urban environments. Our project is available at https://github.com/usail-hkust/CityNav.
Propagation models are essential for modeling and simulating dynamic processes such as epidemics and information diffusion. However, existing tools struggle to scale to large-scale graphs that emerge across social networks, epidemic networks and so on, due to limited algorithmic efficiency, weak scalability, and high communication overhead. We present FS_GPlib, a unified library that enables efficient, high-fidelity propagation modeling on Web-scale graphs. FS_GPlib introduces a dual-acceleration framework: it combines micro-level synchronous message-passing updates with macro-level batched Monte Carlo simulation, leveraging high-dimensional tensor operations for parallel execution. To further enhance scalability, it supports distributed simulation via a novel target-node-based graph partitioning strategy that minimizes communication overhead while maintaining load balance. Theoretically, we show that under ideal assumptions, the runtime of simulations converges approximately to a constant. Extensive experiments demonstrate up to 35,000× speedup over standard libraries such as NDlib and execution of a full Monte Carlo simulation on a Web-scale (billion-edge) graph in 11 seconds while maintaining high simulation fidelity. FS_GPlib supports 29 propagation models—including epidemic and opinion dynamics and dynamic network models—and offers a lightweight Python API compatible with mainstream data science ecosystems. By addressing the unique challenges of modeling diffusion and cascades on the Web, FS_GPlib provides a scalable, extensible, and theoretically grounded solution for large-scale propagation analysis in epidemiology, social media analysis, and online network dynamics. Code available at: https://github.com/Allen-Ciel/FS_GPlib.
Recently, Agentic Reinforcement Learning (Agentic RL) has made significant progress in incentivizing the multi-turn, long-horizon tool-use capabilities of web agents. While mainstream agentic RL algorithms autonomously explore high-uncertainty tool-call steps under the guidance of entropy, excessive reliance on such signals leads to the training collapse. In this paper, we delve into the challenges caused by entropy and propose the Agentic Entropy-Balanced Policy Optimization (AEPO), an agentic RL algorithm designed to balance entropy in both the rollout and policy update phases. AEPO comprises two core components: (1) a dynamic entropy-balanced rollout mechanism that adaptively allocates global and branch sampling budget through entropy pre-monitoring, while imposing a branch penalty on consecutive high-entropy tool-call steps to prevent over-branching issues; and (2) Entropy-Balanced Policy Optimization that inserts a stop-gradient operation into the high-entropy clipping term to preserve and properly rescale gradients on high-entropy tokens, while incorporating entropy-aware advantage estimation to prioritize learning on high-uncertainty tokens. Results across 14 challenging datasets show that AEPO consistently outperforms 7 mainstream RL algorithms. Further analysis reveals that AEPO improves rollout sampling diversity while maintaining stable policy entropy, facilitating scalable training of general web agents. The code is available at https://github.com/RUC-NLPIR/ARPO.
The Group Steiner Tree Problem (GSTP) has been popularly used to formulate graph-based tasks on the Web where the number of groups (i.e., g), e.g., representing the number of keywords in knowledge graph search, is assumed to be small. This assumption never holds in emerging tasks such as the summarization of knowledge graphs, where g represents the number of distinct entity description patterns that increases with graph order (i.e., n) and reaches 105 in practice. Existing algorithms become impractical, since they are optimized for large n but not for large g. In this paper, we devise novel approximation algorithms for GSTP that exhibit scalability in relation to both n and g. When g is large, our algorithms outperform existing algorithms that have a comparable approximation ratio by orders of magnitude in running time, showing their unique ability to practically support such challenging Web applications.
Bipartite graphs are widely used to model relationships between entities of different types, where vertices are divided into two disjoint sets. Biclique-preserving clustering is a fundamental operation that retrieves clusters with dense bicliques, enabling various emerging applications. However, existing methods either fail to accurately capture the unique properties of bipartite graphs or significantly overlook the informative higher-order biclique substructure, leading to compromised clustering quality. Additionally, existing methods are overly dependent on biclique enumeration, resulting in poor scalability. To address these challenges, we propose ECRC, a simple yet provable Edge-Centric Reweighting Clustering framework that provides strict approximation guarantees for any biclique. A key advantage of ECRC is its ability to leverage powerful counting instead of exhaustive enumeration, significantly reducing time and space complexity. To further improve efficiency, we propose several effective graph reduction strategies to eliminate the unqualified vertices and edges before calculating the edge-centric weight. Extensive experiments on five datasets show that our algorithms are more efficient and effective compared to six baselines.
Identifying high-revenue mechanisms that are both dominant strategy incentive compatible (DSIC) and individually rational (IR) is a fundamental challenge in auction design. While theoretical approaches have encountered bottlenecks in multi-item combinatorial auctions, there has been much empirical progress in the automated design of such mechanisms using machine learning. However, existing research primarily focuses on randomized auctions, with less attention given to more practical deterministic auctions. Therefore, in this paper, we introduce OD-VVCA, an objective decomposition approach for automated designing revenue-maximizing deterministic Virtual Valuations Combinatorial Auctions (VVCAs), which are inherently DSIC and IR. We use a parallelizable dynamic programming algorithm to compute the allocation and revenue outcomes of a VVCA efficiently. We then decompose the revenue objective function into continuous and piecewise-constant discontinuous components, optimizing each using distinct methods. Extensive experiments show that OD-VVCA achieves high revenue in multi-item auctions, especially in large-scale settings where it outperforms both randomized and deterministic baselines, indicating its efficacy and scalability.
The performance of modern AI systems is fundamentally constrained by the quality of their underlying GPU kernels, which translate high-level algorithmic semantics into low-level hardware operations. Achieving near-optimal kernels requires expert-level understanding of hardware architectures and programming models, making kernel engineering a critical but notoriously time-consuming and non-scalable process. Recent advances in large language models and LLM-based agents have opened new possibilities for automating kernel generation and optimization. LLMs are well-suited to compress expert-level kernel knowledge that is difficult to formalize, while agentic systems further enable scalable optimization by casting kernel development as an iterative, feedback-driven loop. Rapid progress has been made in this area. However, the field remains fragmented and lacks a systematic perspective for LLM-driven kernel generation. This survey addresses this gap by providing a structured overview of existing approaches, spanning LLM-based approaches and agentic optimization workflows, and systematically organizing the datasets and benchmarks that underpin learning and evaluation in this domain. Moreover, key open challenges and future research directions are further outlined, aiming to establish a comprehensive reference for the next generation of automated kernel optimization. To keep track of this field, we maintain an open-source GitHub repository at https://github.com/flagos-ai/awesome-LLM-driven-kernel-generation.
Motion planning among multiple robots in a shared space is a fundamental yet computationally challenging problem in robotics, with applications ranging from warehouse automation to autonomous fleets. In this work, we introduce a fast, scalable motion planner that achieves real-time, collision-free trajectory planning via a two-staged algorithm combining deterministic search-based planning with machine learning-driven conflict resolution. We present a prioritized Safe Interval Path Planning algorithm (SIPP-PP) with a novel limited goal reservation strategy to prevent goal-blocking conflicts while allowing shared goal regions. We added a second layer of ML-guided Large Neighborhood Search (LNS) procedure to our SIPP-PP algorithm for improving success rates in highly congested environments via intelligent selection of conflict resolution actions. The result is a planning system that generates collision-free paths for multiple robots in complex environments within tens of milliseconds. For example, compared to recent advanced learning-based methods such as diffusion planners, our planner is two-to-three orders of magnitude faster. Our work demonstrates a multi-robot planner capable of real-time operation in dense scenarios, satisfying the stringent requirements of industrial applications such as drive units in fulfillment centers.
Achieving optimal coordination in multiagent systems involves a trade-off between intractable centralized planning and suboptimal decentralized execution. We bridge this gap by introducing Approximate Recursive Small Step-Semi-Decentralized A* (RS-SDA*), a tree search algorithm that exploits time-varying centralization during periods of available communication conditioned on the environment or joint actions. By interleaving offline planning with online search and using relaxed heuristics, RS-SDA* achieves high solution quality with reduced computational overhead. SDec-POMDP benchmark experiments show that Approximate RS-SDA* often finds near exact optimal solutions in less than 1% of the time required by exact algorithms. We show scalability in six labyrinth environments both deterministic and stochastic state transitions, and demonstrate real-world feasibility with a multi-drone search-and-rescue simulation in the DARPA Subterranean Challenge cave system.
This paper studies a risk-sensitive formulation of the multi-robot search problem, termed multi-robot mean-standard deviation search (MuRMSS), in which a team of robots cooperatively search for a moving target by minimizing a linear combination of the mean and standard deviation of search time. However, the standard deviation term is inherently non-additive, making it difficult to estimate, incompatible with canonical multi-robot search algorithms, and preventing consistent decomposition into individual robot utilities, which is essential for scalable multi-robot cooperation. In view of these challenges, we propose MV-FAC, which comprises a mean-variance temporal-difference module that jointly learns the mean and variance of search time, a factorization module that decomposes them into individual utilities, and a decentralized policy optimization module that minimizes each robot’s individual mean-std objective. We further establish and prove the mean-std individual global minimization (MS-IGM) theorem, thereby ensuring consistency between individual- and team-level objectives. Extensive simulation studies on standard multi-robot search benchmarks demonstrate that MV-FAC achieves the best overall mean-std search-time performance. We also validate MV-FAC's practicality by deploying it on a physical multi-robot system for moving target search in a real-world building environment.
Bound-Independent Pruning (BIP) is a powerful technique for accelerating tree-based complete search algorithms for Distributed Constraint Optimization Problems (DCOPs) by pruning dominated regions of the search space using only local information. However, BIP fundamentally relies on constructing a context-dependent dominating space through joint optimization over local constraints, incurring exponential computational and storage complexity that limits its practical scalability. To address this limitation, we propose DR-BIP, a decoupled and sound reformulation of BIP that enables efficient identification of dominated subspaces without explicitly computing the dominating space. By reformulating dominated-subspace detection into pairwise dominance tests and decoupling them across independent constraints, DR-BIP eliminates joint optimization and reduces both computational and storage complexity from exponential to polynomial. The resulting dominance components can be precomputed and reused across context changes, further improving efficiency. We formally prove the correctness of DR-BIP and integrate it into several state-of-the-art tree-based complete DCOP algorithms. Extensive empirical evaluation on standard benchmarks confirms that DR-BIP consistently outperforms BIP, significantly reducing both computation time and communication overhead.
Multi-agent pathfinding (MAPF) under one-shot planning is a core component of warehouse automation, yet classical formulations typically assume four-connected 2D grids with unit-time moves in four directions. To fill reality gaps while still being trackable with discrete combinatorial search, this work proposes a more practical counterpart tailored to differential-drive AGVs. We term this multi-agent warehouse pathfinding (MAWPF), featured with four constraints: (i) agent actions are restricted to straight motion and in-place rotation; (ii) rotations require multi-step costs; (iii) acceleration and deceleration are considered, and; (iv) follower collisions are prohibited to prevent rear-end crashes. To solve MAWPF efficiently, we adapt representative suboptimal MAPF algorithms-PP, LNS2, PIBT, and LaCAM-and conduct comprehensive benchmarking. Our experiments reveal that PP and LNS2 struggle to solve instances with many agents, while PIBT-based approaches achieve preferable scalability with increased solution cost. We believe that these constitute an important step toward adapting classical gridworld MAPF to operational warehouse setups.
Treewidth is a fundamental graph invariant that quantifies how tree-like a given graph is. It is extensively used with dynamic programming to design fixed-parameter tractable algorithms for many NP-hard graph combinatorial optimization problems. However, despite broad theoretical applicability, treewidth dynamic programming (TDP) does not scale in practice beyond graphs with very small treewidth. Rather than applying TDP as a standalone technique, we demonstrate that TDP can serve as a broadly applicable enhancer for a wide range of graph combinatorial optimization algorithms. Our framework leverages the concept of treewidth modulators, which refer to vertex sets whose removal significantly reduces the treewidth. We further propose an empirically efficient procedure for generating such treewidth modulators. To enhance an algorithm 𝒜, we use 𝒜 to heuristically make decisions on the modulators vertices, after which the remaining decisions outside the treewidth modulators become scalable for TDP. To demonstrate the general applicability of our proposed framework. We experimented with three classic graph combinatorial optimization models: Maximum Independent Set, Minimum Vertex Cover, and Max Cut. We apply TDP to enhance algorithms across diverse paradigms, including evolutionary search, greedy heuristics, and graph-neural-network-based heuristics. For all combinations of optimization models and base algorithms, TDP significantly improves performance over the original methods. In many settings, TDP-enhanced greedy heuristics are competitive with, and sometimes clearly outperform, state-of-the-art commercial solvers.