CS Paper Radar

Ellipsoids from Tangents

Efrat Dahan, Michael Werman

cs.CV cs.CG ·submitted 2026-10-11 12:51 UTC · v1
unusual

Abstract

This paper presents an algorithm for detecting and fitting multiple ellipsoids in 2D, 3D and higher-dimensional data. The representation is based on tangents to the ellipsoid together with their contact points, rather than on points alone. A tangent contributes d independent equations where a point contributes one, so each hypothesis needs fewer samples, which in turn reduces the number of iterations required to recover every ellipsoid. The problem is posed as sets of linear equations whose solutions -- the ellipsoid parameters -- are recovered robustly by clustering in parameter space. The algorithm works in all dimensions and outperforms the state of the art in 2D. The approach applies in general to the robust solution of linear equations, and so has utility beyond ellipsoid fitting.

Comment
8 pages, 7 figures. Written in 2016; posted in 2026 with revised exposition. Results unchanged

Closest papers

Nearest neighbours by meaning across the whole index.

Universality and sharp thresholds for ellipsoid fitting

cs.DS math.PRcond-mat.dis-nncs.LG+1 ·2026-08-27 ·Frederic Koehler, Youngtak Sohn
similarity 0.53
Abstract · 79 pages, 4 figures

We establish a sharp phase transition for fitting random vectors by an ellipsoid. The random vectors have independent subgaussian coordinates with mean zero, variance one, and a common fourth moment, and the number of vectors is proportional to the square of the dimension. We identify an explicit satisfiability threshold such that, with high probability, a positive definite ellipsoid passes through every data point below the threshold, whereas no positive semidefinite fit exists above it. We also determine the optimal squared fitting error throughout the unsatisfiable regime. In particular, the threshold depends on the coordinate distributions only through their common fourth moment, revealing a fourth moment universality phenomenon. For standard Gaussian data the threshold is $1/4$, resolving the ellipsoid fitting conjecture.

0.39

RBF Your SDF: Radial Basis Function Interpolation of Signed Distance Fields with Implied Tangent Points

cs.GR ·2026-09-05 ·Yong Cheng, Yotam Gingold
top venue similarity 0.49
Abstract · 19 pages

Signed distance fields (SDFs) are a popular implicit representation of geometry. Converting a discrete set of SDF samples into an explicit surface is a fundamental problem in geometry processing. Traditional reconstruction methods such as marching cubes and dual contouring ignore the geometric information carried by samples far from the surface. Recently, Sellán et al.[2023] and several follow-up works leveraged the tangent-sphere structure of SDFs; every sample implies a point on a sphere tangent to the surface. However, these approaches extract the zero-level set via surface reconstruction, which considers only points and normals on the surface and ignores the remaining samples. We propose an approach that marries the tangent-sphere observation with radial basis function interpolation of all data, the implied surface points and the original data. By detecting spheres with extremely constrained tangent points, a configuration geometrically forced at sharp surface features, we identify and preserve surface corners that surface reconstruction-based methods systematically round. A partition-of-unity decomposition allows our method to scale efficiently to large grid resolutions. Our reconstructions improve both Chamfer and Hausdorff accuracy at every tested resolution.

0.42

Superquadric Primitive Decomposition of 3D point clouds via Geometric-Aware Inlier Refinement

cs.CV ·2026-09-28 ·Alessandro Rinaldi, Edoardo Tedesco, Andrea Ferraris, Filippo Leveni, Daniele Baieri +3 more
top venue similarity 0.49
Abstract · 19 pages, 11 figures, under review

The decomposition of 3D point clouds into interpretable geometric primitives remains a longstanding challenge in Computer Vision and Computer Graphics. Among the available representations, superquadrics offer a compact and expressive model capable of capturing a wide range of shapes. However, their estimation is inherently challenging, as it requires solving a non-linear optimization problem and is particularly sensitive to noise, outliers, and overlapping structures. While robust estimation methods such as RANSAC and its variants achieve strong performance, they rely primarily on spatial proximity and residual-based criteria, often leading to incorrect inlier assignments across adjacent or complex arrangements of primitives. In this work, we introduce a geometric-aware framework for primitive decomposition that explicitly incorporates local surface properties into the fitting process. Specifically, we propose an inlier refinement step formulated as an energy minimization problem and solved via graph-cut optimization. Our formulation integrates geometric priors, such as normal consistency, enabling more reliable inlier selection beyond purely residual-based criteria. The approach naturally applies to both single-model estimation and multi-model decomposition. By leveraging geometric information beyond point-wise residuals, our method reduces erroneous inlier propagation and stabilizes parameter estimation. Experiments on synthetic and real datasets show consistent improvements in geometric accuracy, robustness to noise and outliers, and convergence efficiency compared to state-of-the-art RANSAC-based methods.

0.39

Extrinsic Curvature Estimation by Closest Point Projection of Rays

cs.CG math.DG ·2026-10-24 ·Liangchen Liu, Yen-Hsi Richard Tsai
similarity 0.46
Abstract · 45 pages, 9 figures

We propose a parametrization-free framework for estimating the second fundamental form and the principal curvatures of a submanifold of $\mathbb{R}^d$. The method uses the closest point projections of a few short random rays and recovers the curvature from the curves that these projections induce on the submanifold, without coordinate charts or local fitting. We analyze the geometry of the induced curves and characterize when they are geodesics. For hypersurfaces, these results give two algorithms with error bounds: a least squares reconstruction of the second fundamental form from the curvatures of the induced curves, and a direct estimate of all principal curvatures from the eigenvalues of a $d\times d$ matrix built from $d$ rays, which needs no normal information and costs $\mathcal{O}(d^3)$ besides the projections. In higher codimension, we can also recover the second fundamental form one normal direction at a time. On point clouds, where the projection becomes a nearest neighbor query, we bound the additional error. Experiments confirm the predicted rates for hypersurfaces in up to $128$ dimensions, for surfaces of codimension up to $98$, and on point clouds, demonstrating the effectiveness of the proposed framework in practice.

0.33

Geometric Pairwise Classification of Affine Constraints over Ellipsoidal Regions

eess.SY math.OC ·2026-11-06 ·Igor M. L. Pataro, Martina Mammarella, Fabrizio Dabbene, Teodoro Alamo
similarity 0.46
Abstract · 6 pages, 1 figure

This paper presents a deterministic geometric procedure for analysing affine constraints over fixed ellipsoidal regions, motivated by chance-constrained set approximation. Analytical tests classify inequalities as always violated, never violated, or cutting. Pairwise tests determine whether two inequalities can be strictly violated at a common point, yielding a compatibility matrix. The tests follow from quadratic optimisation and the Karush--Kuhn--Tucker conditions, with explicit treatment of tangencies, parallel normals, and degenerate inequalities. The formulation applies in arbitrary finite dimensions and provides geometric information for subsequent bounds on simultaneous sampled violations and safe-region approximation.

0.29

Manifold-Stable Flow Matching

cs.LG cs.ROeess.SY ·2026-09-28 ·Amirhossein Nazerian, Ali Pezeshki, Jianguo Zhao
hot direction similarity 0.45
Abstract

Flow matching (FM) learns generative dynamics through velocity regression. Geometric FM variants commonly assume a prior supported on the data manifold, requiring geometric knowledge that is often unavailable. Without such knowledge, low regression error alone does not guarantee manifold adherence. Adherence keeps generated samples within valid configurations and is empirically associated with better task performance. We introduce manifold-stable flow matching (MSFM), which can start from an arbitrary ambient prior, not necessarily supported on the manifold. Using tools from nonlinear dynamics, namely contraction theory, MSFM combines learned tangential transport with prescribed normal contraction. The construction uses analytical projectors for known manifolds and local affine proxies estimated by principal component analysis for unknown data geometry. By implementing contraction theory in both cases of known and unknown manifolds, we guarantee manifold invariance and transverse convergence to the manifold within a desired time window (e.g., one second). We derive a family of compatible probability paths and decompose the training loss into a learnable tangential term and a normal residual. An ellipse experiment attains a mean terminal off-manifold error of order $10^{-6}$. In Push-T robotic experiments, MSFM raises success from $74\%$ to $82\%$. In the Robomimic Square task, success increases from $60\%$ to $72\%$, while rotation-manifold deviation decreases from order $10^{-2}$ to $10^{-7}$. The MSFM terminal geometric errors are controlled by the chosen numerical tolerance. These results demonstrate stronger geometric adherence and higher observed task performance, supporting prescribed normal contraction as a complement to learned generative transport.

0.30

Tail-Aware Geometry Learning for Conformal Ellipsoids

cs.LG ·2026-09-23 ·Xiang Zhang
similarity 0.44
Abstract

This paper studies multivariate conformal prediction (CP), a distribution-free uncertainty quantification framework with finite-sample coverage guarantees. The efficiency of multivariate prediction sets hinges critically on the residual geometry encoded by the nonconformity score, while existing minimum-volume methods rely on quantile thresholds that ignore tail residual severity and implicitly bind geometry learning to coverage level. We propose a tail-aware geometry learning framework for conformal ellipsoids that decouples tail sensitivity in geometry learning from the final coverage guarantee. Using a two-split design, we learn the metric matrix via volume minimization under a CVaR constraint on an estimation split, then apply standard conformal calibration on a held-out calibration split. The resulting problem is convex and admits a bounded-reweighting interpretation that prioritizes high-residual samples. Moreover, we theoretically characterize the trade-off between ellipsoidal volume and tail severity. Experimental results demonstrate the effectiveness of the proposed method.

0.22

PnP*: A certifiable solver for Perspective-n-Point

cs.CV cs.ROmath.OC ·2026-10-22 ·Bang-Shien Chen, Caitrin E. Eaton, David M. Rosen
theory similarity 0.44
Abstract · 28 pages, 3 figures

Estimating a camera pose from 3D-2D correspondences - Perspective-n-Point - is one of the most fundamental problems in computer vision. Existing methods either solve a minimal problem or replace the objective with an easier one. Surprisingly, no scalable certifiable solver for the actual Maximum Likelihood Estimation (MLE) exists. We propose PnP*, the first practical solver that guarantees efficient computation and returns a certifiable globally optimal solution. We prove that the underlying convex relaxation is exact under moderate noise, which to our knowledge is the first stability guarantee for any relaxation for the MLE of PnP. Furthermore, we reduce the relaxation by exploiting chordal sparsity pattern and quotient ring reduction such that the relaxation is tractable and scalable. The stability and scalability results are verified numerically, as PnP* returns a provably correct camera pose at over 10 Hz.

0.19