CS Paper Radar

Equivalent Graphical Conditions for Angle Rigidity and Angle-Based Network Localization

Jinpeng Huang, Gangshan Jing, Kai Zhao, Yongduan Song

cs.IT math.OC ·submitted 2026-11-02 08:46 UTC · v1

Abstract

Angle rigidity theory provides a theoretical basis for characterizing the geometric shape of graphs embedded in the plane under angle constraints, and establishing global convergence of angle-based network localization algorithms. The related references, however, are largely restricted to graphs generated by triangulation or bilateration ordering, which are sufficient but not necessary for angle rigidity. This paper addresses this challenge by focusing on establishing the equivalence between angle constraints and bearing constraints. The conditions for cycle compatible frameworks (with possibly non-generic configurations) to be angle fixable are provided. Moreover, it is shown for the first time that Laman graphs equivalently characterize minimally globally angle rigid graphs, implying that a Laman graph is the simplest graph that allows a generic embedding in the plane to be uniquely determined by subtended angles. As an application, a distributed algorithm for angle-based sensor network localization is proposed, which guarantees global convergence under a much milder network topology condition than those in the literature.

Closest papers

Nearest neighbours by meaning across the whole index.

Destroying Rigidity in the Plane

cs.DM ·2026-10-28 ·Yu Cong, Chao Xu, Yajie Zhao
theory similarity 0.59
Abstract

Rigidity and global rigidity are fundamental graph properties in discrete geometry, with applications to structural engineering and network localization. In two dimensions, both admit combinatorial characterizations in terms of the rigidity matroid and graph connectivity. We study the computational complexity of finding minimum-cost sets of edges or vertices whose deletion destroys either property in a finite simple graph. With unit costs, we give deterministic polynomial-time algorithms for edge deletion destroying global rigidity and vertex deletion destroying either property. We prove that edge deletion destroying rigidity is NP-hard and that, with positive integer costs, all four problems are NP-hard. These results resolve, in dimension two, the open questions on recognizing robustness under edge and vertex deletions posed by Jordán and Whiteley (2017), as well as the minimum edge-deletion problem for rigidity recorded in EGRES Open.

0.42

Ollivier's Ricci Curvature on Complex-weighted Graphs

cs.SI math.MGphysics.soc-ph ·2026-08-10 ·Yu Tian, Eleanor Wiesler, Melanie Weber
similarity 0.54
Abstract · 32 pages, 11 figures

Understanding the geometry of complex networks is critical for effective modeling and analysis across domains. While discrete notions of Ricci curvature have emerged as powerful tools for characterizing both local and global network structure, existing formulations are largely confined to undirected networks with real-valued weights. This limits the use of curvature-based analysis of directional and complex-weighted relations that arise naturally in many applications, from social and biological systems to quantum and signal-processing networks. In this work, we introduce a principled extension of Ollivier's Ricci curvature to complex-weighted graphs, which encompasses directed graphs as a special case. We establish fundamental theoretical properties of this new notion, including relations to the magnetic Laplacian and combinatorial upper and lower bounds that relate curvature to cycle structure in local neighborhoods. We further develop computational methods for curvature estimation and demonstrate their utility in community detection on directed networks.

0.10

Macroscopic Motion Patterns from Generalized Velocity Rigidity in Multi-Agent Networks

eess.SY ·2026-09-16 ·Ronghai He, Changhuang Wan
theory similarity 0.52
Abstract · 8 pages, 7 figures

Traditional graph rigidity theory enforces structural constraints in the position space, effectively restricting a multi-agent formation to a static geometric shape. In this paper, we introduce a fundamental paradigm shift by applying rigidity constraints directly to the agents' continuous-time velocity space. We propose the concept of generalized velocity rigidity, demonstrating that the macroscopic physical motion patterns of a multi-agent network are entirely dictated by the underlying static graph topology. By strictly confining the network's acceleration profile to the null space of the velocity rigidity matrix, we mathematically map the trivial motions of this null space into exact physical trajectories. Specifically, we prove that translational, rotational, and scaling trivial motions seamlessly integrate into cohesive curved flocking, synchronized helical and circular $\mathrm{SO}(d)$ orbiting, and exponential spatial homothety, respectively. Furthermore, we analyze velocity-space singularities, showing that velocity consensus induces a valid topological contraction rather than a structural failure. Finally, we provide comprehensive numerical simulations to validate these theoretical mappings, demonstrating that complex macroscopic maneuvers can be orchestrated purely through algebraic constraints in the velocity space, unlocking unprecedented spatial shape flexibility for multi-agent swarms.

0.25

Unified Constrained Geometric Configuration Optimization for Source Localization Systems: A Riemannian Manifold-Based Approach

eess.SP ·2026-09-11 ·Xin Cheng, Feng Shu, Gangle Sun, Xinrui Li, Yuqi Chen +1 more
similarity 0.50
Abstract

Time of arrival (TOA), time difference of arrival (TDOA), received signal strength (RSS), received signal strength difference (RSSD) and angle of arrival (AOA) are commonly used techniques for source localization. The positioning accuracy of these systems depends heavily on the geometric configuration of sensors, which is typically constrained by practical conditions. This paper presents a unified framework for optimizing sensor geometry across all five localization systems, explicitly incorporating both distance and angle constraints on sensor positions. First, the Cramér-Rao lower bounds (CRLBs) of these systems are transformed to obtain a unified expression. Based on this expression, a unified constrained geometric configuration optimization problem is formulated. The problem is then simplified into a compact form by replacing the sensor-target angles with an orientation matrix. Subsequently, a Riemannian manifold-based constrained geometric configuration optimization algorithm (RM-CGCOA) is proposed to optimize the sensor-target distances and the orientation matrix. This algorithm casts the orientation matrix onto a product manifold of unit circles. An adaptive pullback is further proposed to strictly enforce angle-related inequality constraints, ensuring that all iterates remain feasible when updating the orientation matrix via the Riemannian gradient. Within RM-CGCOA, analytical optimal distances are derived for TOA, TDOA, RSS and AOA, whereas for RSSD, the distances are updated using projected gradient descent (PGD) together with the orientation matrix. Experimental results demonstrate that the proposed RM-CGCOA consistently achieves a significantly lower position error bound (PEB) compared with the existing strategies and yields a similar PEB to the near-optimal search algorithm, but with a much faster running time.

0.22

Global Optimality of Pose Graph Optimization

cs.RO eess.SP ·2026-10-10 ·Shuan Ding, Ruishuang Chen, Mengfan Cao, Zaiyue Yang
theory similarity 0.50
Abstract

Pose Graph Optimization (PGO) is a classical and widely applied problem in state estimation for robotics, playing a fundamental role in localization, mapping, and navigation. Yet, it is nonconvex in nature and may have many local minimizers, thus difficult to analyze. In this paper, we investigate the optimization landscape and establish a sufficient condition of global optimality for PGO. The ultimate goal of this paper is to theoretically confirm that the optimization landscape is benign and attractive around the global minimizer, if noise is smaller than an explicit and a priori bound. To reveal such an insight, this paper develops three main technical results. First, we identify a proper basin of attraction (BOA) containing global minimizer, and characterize its geometric property by showing that its radius is controlled by noise in an explicit way. Then, by exploring the first order optimality conditions of PGO, we prove that a local minimizer is globally optimal if a noise-controlled criterion is satisfied. Finally, by combining above two results, we prove that one and only one local minimizer exists in the BOA and this minimizer is globally optimal, when the noise is smaller than an explicit bound that can be verified a priori. Numerical simulations validate the proposed theory under various random cases, showing that the obtained conditions provide an effective criterion for certifying the global optimality of PGO.

0.36

A Geometry-Driven, Framework-Agnostic Optimization for Object Pose Estimation

cs.CV ·2026-08-27 ·Wei Chen, Tao Zhen, Zhongchen Shi, Jing Zhang, Liang Xie +1 more
similarity 0.49
Abstract · Submitted to TPAMI, under review

Current object pose estimation research remains predominantly model-centric, focusing on architectural innovations and post-processing refinements. This paper introduces a data-centric optimization by proposing a novel, physically grounded rotation representation through principal axes alignment. Our method aligns the object's coordinate system with its inherent geometric axes, derived from inertial properties, yielding three key advantages: Inherent Stability-leveraging the energy-minimizing property of principal axes provides a robust representation that is less sensitive to noise and occlusions; Symmetry-Aware Canonicalization-explicitly resolving rotational ambiguities for symmetric objects at the data level, which fundamentally eliminates label confusion during network training; and Framework Agnosticism-the optimization is applied purely at the dataset level, ensuring plug-and-play compatibility with existing networks without any architectural modification. We validate the framework across diverse category-level and instance-level models. Extensive experiments demonstrate consistent and significant accuracy improvements, while preserving the integrity of the baseline network. This work establishes a new, geometry-driven direction for enhancing pose estimation, circumventing the need for complex network redesign.

0.15

Discretization-free exact recovery in geometric community detection

cs.SI math.PR ·2026-08-23 ·Maarten Hoeneveld, Moritz Otto, Raphaël Sala
theory similarity 0.48
Abstract · 30 pages, 2 figures

Geometric community detection seeks to recover latent communities in networks where connectivity depends jointly on community structure and continuous spatial geometry. Existing exact-recovery approaches typically discretize the underlying space, which can impose restrictive structural assumptions on the connectivity functions. We develop a polynomial-time, discretization-free algorithm for exact recovery in the Geometric Hidden Community Model (GHCM), operating directly on the continuous geometry. Our method succeeds even when connectivity functions coincide on a nontrivial portion of their visibility range and when two communities can be distinguished only through their connectivity to a third community. We prove exact recovery under these weaker conditions and provide experiments showing that the algorithm succeeds beyond the theoretically guaranteed regime.

0.23

Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry

cs.CV cs.CGcs.LGcs.RO+1 ·2026-10-07 ·Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome
theory similarity 0.48
Abstract · 67 pages, 20 figures. Includes full proofs and experimental appendices

Procrustes-Wasserstein alignment jointly estimates a matching and rotation without supplied correspondences, but alternating minimization can stop at suboptimal solutions. Rubix solves the equally weighted planar problem globally under squared Euclidean loss. Each matching $σ$ of two centered $n$-point sets defines a complex correlation $z_σ=\sum_i\bar x_i y_{σ(i)}$. Their convex hull is the permutation polygon: supporting vertices give optimal matchings at fixed rotations, and the farthest vertex gives the global alignment. We prove the sharp bound of $n(n-1)$ vertices for $n\ge2$, answering Rote's rotation-assignment open problem. In exact arithmetic, assignment queries recover the polygon in $\mathcal O(n^5)$ operations. Assignment-based bounds extend the approach to three-dimensional rotations and partial matching at a supplied translation through branch-and-bound. On timed MPEG-7 shape pairs, Rubix attains every numerical reference value in 12 ms on average, 50 times faster than a rotation grid at the same accuracy. Its distances improve gravity-aligned matching of real 3D scans, shape retrieval and noisy crystal classification over alternating minimization.

0.25