Abstract We present ParaMG, a surface multigrid method that restores classical multigrid structure on curved surfaces by expressing all hierarchy levels in a single globally consistent planar domain. Existing surface multigrid methods rely on composed local parameterizations or 3D projections for cross‐level transfer, requiring repeated per‐level local approximations that can degrade convergence. Our key insight is that a global conformal parameterization with cone singularities provides a shared coordinate system with low, controllable distortion, where prolongation reduces to exact planar barycentric interpolation. We construct the hierarchy directly in this domain using a seam‐aware simplification strategy, yielding sparse prolongation matrices with three entries per row. ParaMG converges in fewer V‐cycles than prior surface multigrid methods and delivers substantial speedups in applications with changing linear systems, including geometric flows, thin‐shell simulation, and polycube deformation.

The Walk on Spheres (WoS) algorithm is a mesh-free and highly flexible Monte Carlo method for solving partial differential equations, but its practical applicability is limited by slow O ( N -1/2 ) convergence. While prior variance reduction techniques exploit spatial correlations through integral properties of the PDE, they do not fully utilize the intrinsic Markov structure of the WoS process. We introduce a new variance reduction framework based on reusing intermediate states along each random walk. Leveraging the Markov property, we show that every point visited by a WoS trajectory provides a valid unbiased estimator, but its direct use is hindered by the complex distribution induced by dynamically generated spheres. To resolve this, we propose the Walk on Probes (WoP) algorithm, which replaces dynamic spheres with a set of fixed, pre-distributed spherical probes inside the domain. This converts the intractable distribution of path points into samples on fixed boundaries, enabling efficient evaluation through the Poisson integral formula. We further develop a specialized method that combines control variates with self-normalization to further reduce variance. Together, these components substantially improve sample efficiency while preserving the flexibility of WoS. Code and data for this paper are at https://github.com/USTCGCL-WoS/Walk-on-Probes.

We propose an efficient method to compute a small set of integer-constrained cone singularities, which induce a rotationally seamless conformal parameterization with low distortion. Since the problem only involves discrete variables, i.e., vertex-constrained positions, integer-constrained angles, and the number of cones, we alternately optimize these three types of variables to achieve tractable convergence. Central to high efficiency is an explicit construction algorithm that reduces the optimization problem scale to be slightly greater than the number of integer variables for determining the optimal angles with fixed positions and numbers, even for high-genus surfaces. In addition, we derive a new derivative formula that allows us to move the cones, effectively reducing distortion until convergence. Combined with other strategies, including repositioning and adding cones to decrease distortion, adaptively selecting a constrained number of integer variables for efficient optimization, and pairing cones to reduce the number, we quickly achieve a favorable tradeoff between the number of cones and the parameterization distortion. We demonstrate the effectiveness and practicability of our cones by using them to generate rotationally seamless and low-distortion parameterizations on a massive test data set. Our method demonstrates an order-of-magnitude speedup (30× faster on average) compared to state-of-the-art approaches while maintaining comparable cone numbers and parameterization distortion.

Computing the Laplace–Beltrami operator on point clouds is essential for tasks such as smoothing and shape analysis. Unlike meshes, determining the Laplace–Beltrami operator on point clouds requires establishing neighbors for each point. However, traditional k -nearest neighbors (k-NN) methods for estimating local neighborhoods often introduce spurious connectivities that distort the manifold topology. We propose a novel approach that leverages persistent homology to refine the neighborhood graph by identifying and removing erroneous edges. Starting with an initial k-NN graph, we assign weights based on local tangent plane estimations and construct a Vietoris–Rips complex. Persistent homology is then employed to detect and eliminate spurious edges through a topological optimization process. This iterative refinement results in a more accurate neighborhood graph that better represents the underlying manifold, enabling precise discretization of the Laplace–Beltrami operator. Experimental results on various point cloud datasets demonstrate that our method outperforms traditional k-NN approaches by more accurately capturing the manifold topology and enhancing downstream computations such as spectral analysis.

Smart contracts are essential tools for enabling interaction between blockchain and Internet of Things (IoT) systems. For example, in cold chain logistics, the blockchain can obtain the states of the logistics system through smart contracts. However, direct interactions between smart contracts and these systems introduce uncertainties, potentially leading to network forks or state inconsistencies, which can compromise the security and reliability of the blockchain. To address these challenges, a novel smart contract variable, ExState, is proposed, specifically designed to track and store the dynamic states of IoT systems. Additionally, a corresponding operational logic is defined to organize these states into sequential records, ensuring that the state sequences obtained by each node remain consistent, effectively mitigating state conflicts. In addition, a formal model is developed, accompanied by a theoretical analysis of its determinacy. Experimental results demonstrate that, in cross-chain scenarios, this method achieves a performance improvement of up to 50.41% compared to the traditional Oracle method.

We propose a novel method to generate developable approximations for triangular meshes. Instead of fitting the Gauss image using a geodesic circle in the local neighborhood, we apply a nonlinear dimensionality reduction method, called Isomap, to use a general curve on the sphere for fitting. This brings us a larger space to represent the Gauss image in the local neighborhood as a 1D structure. Specifically, each triangle is assigned a target normal after local fitting; then, we deform the mesh to approach the target normal globally. By iteratively performing fitting and deformation, we obtain the developable approximation. We demonstrate the feasibility and effectiveness of our method over various examples. Compared to the state-of-the-art methods, our results exhibit a higher fidelity to the input mesh while possessing more prominent and visually distinct undevelopable seam curves.

Abstract We propose a novel method for generating symmetric piecewise developable approximations for shapes in approximately global reflectional or rotational symmetry. Given a shape and its symmetry constraint, the algorithm contains two crucial steps: (i) a symmetric deformation to achieve a nearly developable model and (ii) a symmetric segmentation aided by the deformed shape. The key to the deformation step is the use of the symmetric implicit neural representations of the shape and the deformation field. A new mesh extraction from the implicit function is introduced to construct a strictly symmetric mesh for the subsequent segmentation. The symmetry constraint is carefully integrated into the partition to achieve the symmetric piecewise developable approximation. We demonstrate the effectiveness of our algorithm over various meshes.

We propose a simple yet effective method to orient normals for point clouds. Central to our approach is a novel optimization objective function defined from global and local perspectives. Globally, we introduce a signed uncertainty function that distinguishes the inside and outside of the underlying surface. Moreover, benefiting from the statistics of our global term, we present a local orientation term instead of a global one. The optimization problem can be solved by the commonly used numerical optimization solver, such as L-BFGS. The capability and feasibility of our approach are demonstrated over various complex point clouds. We achieve higher practical robustness and normal quality than the state-of-the-art methods.

We propose a practical method to construct sparse integer-constrained cone singularities with low distortion constraints for conformal parameterizations. Our solution for this combinatorial problem is a two-stage procedure that first enhances sparsity for generating an initialization and then optimizes to reduce the number of cones and the parameterization distortion. Central to the first stage is a progressive process to determine the combinatorial variables, i.e., numbers, locations, and angles of cones. The second stage iteratively conducts adaptive cone relocations and merges close cones for optimization. We extensively test our method on a data set containing 3885 models, demonstrating practical robustness and performance. Our method achieves fewer cone singularities and lower parameterization distortion than state-of-the-art methods.

We propose an efficient method to construct sparse cone singularities under distortion-bounded constraints for conformal parameterizations. Central to our algorithm is using the technique of shape derivatives to move cones for distortion reduction without changing the number of cones. In particular, the supernodal sparse Cholesky update significantly accelerates this movement process. To satisfy the distortion-bounded constraint, we alternately move cones and add cones. The capability and feasibility of our approach are demonstrated over a data set containing 3885 models. Compared with the state-of-the-art method, we achieve an average acceleration of 15 times and slightly fewer cones for the same amount of distortion.

We propose a novel method to compute high-quality piecewise developable approximations for triangular meshes. Central to our approach is an evolutionary genetic algorithm for optimizing the combinatorial and discontinuous fitness function, including the approximation error, the number of patches, the patch boundary length, and the penalty for small patches and narrow regions within patches. The genetic algorithm's operations (i.e., initialization, selection, mutation, and crossover) are explicitly designed to minimize the fitness function. The main challenge is evaluating the fitness function's approximation error as it requires developable patches, which are difficult or time-consuming to obtain. Resolving the challenge is based on a critical observation: the approximation error and the mapping distortion between an input surface and its developable approximation are positively correlated empirically. To efficiently measure distortion without explicitly generating developable shapes, we creatively use conformal mapping techniques. Then, we control the mapping distortion at a relatively low level to achieve high shape similarity in the genetic algorithm. The feasibility and effectiveness of our method are demonstrated over 240 complex examples. Compared with the state-of-the-art methods, our results have much smaller approximation errors, fewer patches, shorter patch boundaries, and fewer small patches and narrow regions.

We propose a novel method to generate sparse integer-constrained cone singularities with low distortion constraints for conformal parameterizations. Inspired by [Fang et al. 2021; Soliman et al. 2018], the cone computation is formulated as a constrained optimization problem, where the objective is the number of cones measured by the ℓ 0 -norm of Gaussian curvature of vertices, and the constraint is to restrict the cone angles to be multiples of π /2 and control the distortion while ensuring that the Yamabe equation holds. Besides, the holonomy angles for the non-contractible homology loops are additionally required to be multiples of π /2 for achieving rotationally seamless conformal parameterizations. The Douglas-Rachford (DR) splitting algorithm is used to solve this challenging optimization problem, and our success relies on two key components. First, replacing each integer constraint with the intersection of a box set and a sphere enables us to manage the subproblems in DR splitting update steps in the continuous domain. Second, a novel solver is developed to optimize the ℓ 0 -norm without any approximation. We demonstrate the effectiveness and feasibility of our algorithm on a data set containing 3885 models. Compared to state-of-the-art methods, our method achieves a better tradeoff between the number of cones and the parameterization distortion.

We propose a novel method to compute a piecewise mesh with a few developable patches and a small approximation error for an input triangular mesh. Our key observation is that a deformed mesh after enforcing discrete developability is easily partitioned into nearly developable patches. To obtain the nearly developable mesh, we present a new edge-oriented notion of discrete developability to define a developability-encouraged deformation energy, which is further optimized by the block nonlinear Gauss-Seidel method. The key to successfully applying this optimizer is three types of auxiliary variables. Then, a coarse-to-fine segmentation technique is developed to partition the deformed mesh into a small set of nearly discrete developable patches. Finally, we refine the segmented mesh to reduce the discrete Gaussian curvature while keeping the patches smooth and the approximation error small. In practice, our algorithm achieves a favorable tradeoff between the number of developable patches and the approximation error. We demonstrate the feasibility and practicability of our method over various examples, including seventeen physical manufacturing models with paper.

A geometric mapping establishes a correspondence between two domains. Since no real object has zero or negative volume, such a mapping is required to be inversion-free. Computing inversion-free mappings is a fundamental task in numerous computer graphics and geometric processing applications, such as deformation, texture mapping, mesh generation, and others. This task is usually formulated as a non-convex, nonlinear, constrained optimization problem. Various methods have been developed to solve this optimization problem. As well as being inversion-free, different applications have various further requirements. We expand the discussion in two directions to (i) problems imposing specific constraints and (ii) combinatorial problems. This report provides a systematic overview of inversion-free mapping construction, a detailed discussion of the construction methods, including their strengths and weaknesses, and a description of open problems in this research field.

We propose a novel method to generate sparse cone singularities with bounded distortion constraints for conformal parameterizations. It is formulated as minimizing the ℓ 0 -norm of Gaussian curvature of vertices with hard constraints of bounding the distortion that is measured by the ℓ 2 -norm of the log conformal factor. We use the reweighted ℓ 1 -norm to approximate the ℓ 0 -norm and solve each convex weighted ℓ 1 minimization subproblem by the Douglas-Rachford (DR) splitting scheme. To quickly generate sparse cones, we modify DR splitting by weighting the ℓ 2 -norm of the proximal mapping to force the small Gaussian curvature to quickly approach zero. Accordingly, compared with the conventional DR splitting, the modified method performs one to two orders of magnitude faster. Besides, we perform variable substitution of log conformal factors to simplify the computation process for acceleration. Our algorithm is able to bound distortion to compute sparse cone singularities, so that the resulting conformal parameterizations achieve a favorable tradeoff between the area distortion and the number of cones. We demonstrate its effectiveness and feasibility on a large number of models.

The papers in this special issue focus on trustworthiness in multimedia communications. Recently, social multimedia content is being delivered to users with a high quality of experience (QoE) with the advance of multimedia technologies and social networks. However, as a huge amount of social users have various demands to exchange and share multimedia content with each other, it becomes a new challenge for the current social multimedia analytics and delivery to deal with the various attacks perpetrated by malicious users or through spam contents. Therefore, the trust and risk management for social multimedia content based on the social tie of users become of prime importance to face the unpredicted threats and subsequent damage. This Special Section aims to provide a premier forum for researchers working on the trust-based social multimedia analytics and delivery. It also provides the opportunity for both academic and industrial researchers to discuss recent results and provide solutions to the above-mentioned challenges.

3D printing, also called additive manufacturing, has been increasingly popular and printing efficiency has become more critical. To print artifacts faster with less material, thus leading to lighter and cheaper printed products, various types of void structureshave been designed and engineered inside of shape models. In this paper, we present a novel method for generating support-free elliptic hollowing for 3D shapes which can entirely avoid additional supporting structures. To achieve this, we perform the ellipse hollowing in one of the cross sectional polygons and then extrude the hollowed ellipses to the other parallel cross sections. To efficiently pack the ellipses in the polygon, we construct the Voronoi diagram of ellipses to reason the free-space around the ellipses and other geometric features by taking advantage of the available algorithm for the efficient and robust construction of the Voronoi diagram of circles. We demonstrate the effectiveness and feasibility of our proposed method by designing and printing support-free hollow for various 3D shapes using Poretron, the program which computes the hollow by embedding appropriate APIs of the Voronoi Diagram Machine library that is freely available from Voronoi Diagram Research Center. It takes a 3D mesh model and produces an STL file which can be either fed into a 3D printer or postprocessed.

This paper purposes a global optimization method that could be applied in parameter estimation of wind generation unit model. When complex nonlinear models, like a wind generation unit model are used, the parameter estimation based on local optimization methods, such as nonlinear least squares method or Newton's method, may not be able to find parameter values with acceptable accuracy. The global optimization method, named Hyperbolic Cross Point (HCP) method, is proposed to find good initial parameter values that are used as the starting values, to make parameter estimation based on iterative local optimization methods, converge to accurate parameter values. The paper concludes with two case studies which demonstrate application of the HCP in conjunction with local optimization method, where the results obtained are confirmed to be the globally best solution.

We study the problem of landmark selection for landmark-based routing in a network of fixed wireless communication nodes. We present a distributed landmark selection algorithm that does not rely on global clock synchronization, and a companion local greedy landmark-based routing scheme. We assume no node location information, and that each node can communicate with some of its geographic neighbors. Each node is named by its hop count distances to a small number of nearby landmarks. Greedy routing at a node is performed to equalize its vector of landmark distances to that of the destination. This is done by following the shortest path to the landmark that maximizes the ratio of its distances to the source and the destination. In addition, we propose a method to alleviate the difficulty in routing to destinations near the boundaries by virtually expanding the network boundaries. The greedy routing, when combined with our landmark selection scheme, has a provable bounded path stretch relative to the best path possible, and guarantees packet delivery in the continuous domain. In the discrete domain, our simulations show that the landmark selection scheme is effective, and the companion routing scheme performs well under realistic settings. Both the landmark selection and greedy routing assumes no specific communication model and works with asymmetric links. Although some of the analysis are non-trivial, the algorithms are simple, flexible and cost-effective enough to warrant a real-world deployment.

Abstract — For a wide variety of sensor network environments, location information is unavailable or expensive to obtain. We propose a location-free, lightweight, distributed, and data-centric storage/retrieval scheme for information producers and information consumers in sensor networks. Our scheme is built upon the Gradient Landmark-Based Distributed Routing protocol (GLIDER) [8], a two-level routing scheme where sensor nodes are partitioned into tiles by their graph distances to a small set of local landmarks so that localized and efficient routing can be achieved inside and across tiles. Our information storage and retrieval scheme uses two ideas on top of the GLIDER hierarchy — a distributed hash table on the combinatorial tile adjacency graph and a double-ruling scheme within each tile. Queries follow a path that will provably reach the data replicated by the producer(s). We show that this scheme compares favorably with previously proposed schemes, such as Geographic Hash Tables (GHT), providing comparable data storage performance and better locality-aware data retrieval performance. More importantly, this scheme uses no geographic information, makes few assumptions on the network model, and achieves better load balancing and structured data processing and aggregation even for sensor fields with complex geometric shapes and non-trivial topology. I.

We present a robust approach to data collection, aggregation, and dissemination problems in sensor networks. Our method is based on the idea of a sweep over the network: a wavefront that traverses the network, passes over each node exactly once, and performs the desired operation(s). We do not require global information about the sensor field such as node locations. Instead, in a preprocessing phase, we compute a potential function over the network whose gradients guide the sweep process. The sweep itself operates asynchronously, using only local operations to advance the wavefront. The gradient information provides a local ordering of the nodes that helps reduce the number of MAC-layer collisions as the wavefront advances, while also globally shaping the wavefront so as to conform to the sensor field layout. The approach is robust to both link volatility and node failures that may be present in real network conditions. The potential is computed by a stable diffusion process in which each node repeatedly set its potential to the average of the potentials of its neighbors. Aggregation paths are decided on-line as the sweep proceeds and no fixed tree structure is needed over the course of the computation. We present simulation results illustrating the correctness of the algorithm and comparing the performance of the sweep to aggregation trees under various network conditions.

We present gradient landmark-based distributed routing (GLIDER), a novel naming/addressing scheme and associated routing algorithm, for a network of wireless communicating nodes. We assume that the nodes are fixed (though their geographic locations are not necessarily known), and that each node can communicate wirelessly with some of its geographic neighbors - a common scenario in sensor networks. We develop a protocol which in a preprocessing phase discovers the global topology of the sensor field and, as a byproduct, partitions the nodes into routable tiles - regions where the node placement is sufficiently dense and regular that local greedy methods can work well. Such global topology includes not just connectivity but also higher order topological features, such as the presence of holes. We address each node by the name of the tile containing it and a set of local coordinates derived from connectivity graph distances between the node and certain landmark nodes associated with its own and neighboring tiles. We use the tile adjacency graph for global route planning and the local coordinates for realizing actual inter- and intra-tile routes. We show that efficient load-balanced global routing can be implemented quite simply using such a scheme.

Many algorithms for routing in sensor networks exploit greedy forwarding strategies to get packets to their destinations. We study a fundamental difficulty such strategies face: the "local minimum phenomena" that can cause packets to get stuck. We give a definition of stuck nodes where packets may get stuck in greedy multi-hop forwarding, and develop a local rule, the TENT rule, for each node in the network to test whether a packet can get stuck at that node. To help the packets get out of stuck nodes, we describe a distributed algorithm, BOUNDHOLE, to build routes around holes, which are connected regions of the network with boundaries consisting of all the stuck nodes. We show that these hole-surrounding routes can be used in many applications such as geographic routing, path migration, information storage mechanisms and identification of regions of interest.

This paper presents a new group communication scheme, roamingcast, for collaborative information processing in wireless sensor networks. Roamingcast enables efficient communication among a subset of mobile terminals in a collaboration group. Unicast and multicast communication can be considered as special cases of roamingcast in which the subset contains one and all group members, respectively. We propose a Roaming Hub Based Architecture (RoamHBA, pronounced as 'rumba') as one solution to support roaming-cast. We present the distributed construction and dynamic update of a multicast tree, referred as the roaming hub. This roaming hub has the property that an average pair of terminals communicate using the hub with only constant degradation in path length compared to the best possible path. We have developed network layer protocols implementing this mechanism and evaluated their performance in comparison with roaming restricted flooding. We simulated our design using NS-2.

The development of lightweight sensing andcommunication protocols is a key requirement for designing resource constrained sensor networks. This paper introduces a set of efficient protocols and algorithms, DAM, EBAM, and EMLAM, for constructing and maintaining sensor aggregates that collectively monitor target activity in the environment. A sensor aggregate comprises those nodes in a network that satisfy a grouping predicate for a collaborative processing task. The parameters of the predicate depend on the task and its resource requirements. Since the foremost purpose of a sensor network is to selectively gather information about the environment, the formation of appropriate sensor aggregates is crucial for optimally allocating resources to sensing and communication tasks.This paper makes minimal assumptions about node onboard processing and communication capabilities so as to allow possible implementations on resource-constrained hardware. Factors affecting protocol performance are discussed. The paper presents simulation results showing how the protocol performance varies as key network and task parameters are varied. It also provides probabilistic analyses of network behavior consistent with the simulation results. The protocols have been experimentally validated on a sensor network testbed comprising 25 Berkeley MICA sensor motes.