CS Paper Radar

ToPos: Automated Optimal Positioning on Topographic Manifolds using Constrained Geodesic Voronoi Decomposition

Rajesh Raveendran, Akseli Vanhamaa, Jaakko Suutala, Antti Tikanmäki, Juha Röning

cs.RO ·submitted 2026-09-04 12:38 UTC · v1
published

Abstract

Reliable autonomous mapping, environmental sampling, last-mile logistics, and infrastructure deployment depend on the optimal surface area-balanced distribution of Spatial Reference Sites (SRS). Conventional 2D Euclidean methods often fail in high-relief environments by neglecting topographic variations and physical obstructions. This leads to significant planimetric distortion, spatial clustering, and the placement of targets in inaccessible or shadowed regions, compromising both data integrity and operational safety. This paper introduces ToPos, an automated framework for TOPography-aware Optimal Sampling on topographic manifolds. We treat the terrain as a discrete 2-dimensional manifold embedded in 3D Euclidean space and replace standard flat-map distances with non-Euclidean geodesic distances that follow the actual surface geometry. The point distribution is formulated as an optimization problem using a Constrained Geodesic Voronoi Decomposition, solved via a Riemannian Nesterov Accelerated Gradient (NAG) engine. Our approach restricts target locations to a feasible "safe zone," accounting for non-traversable slopes, vegetation, environmental occlusions, etc. Through evaluations on non-convex sinusoidal manifolds, we show that ToPos mitigates planimetric distortion by utilizing geodesic metrics. This approach results in a $\sim$74% improvement in optimal surface area-balanced distribution, as measured by the coefficient of variation (CV) of the Voronoi cell areas. The framework is architected as a Geographic Information System (GIS)-ready micro-service to bolster the mentioned applications. Index Terms: Topographic Manifolds, Geodesic Voronoi Decomposition, Infrastructure Deployment, 3D Mapping, Spatial Sampling, and Non-Euclidean Optimization.

Comment
©2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works
Journal ref
Proc. IEEE 22nd International Conference on Automation Science and Engineering (CASE), 2026
DOI
10.1109/CASE69030.2026.11704419

Closest papers

Nearest neighbours by meaning across the whole index.

SGE: Semantically-Guided Exploration for Unstructured Environments via Image-Space Waypoint Sampling

cs.RO cs.AI ·2026-08-29 ·Christopher Tatsch, Yu Gu
similarity 0.59
Abstract

This work introduces Semantically-Guided Exploration (SGE), a modular exploration framework for ground vehicles that integrates pixel-level semantic segmentation into sampling-based waypoint selection and receding-horizon route optimization. Unlike conventional geometric exploration methods, SGE evaluates candidate exploration goals directly in the image space using a semantic-aware utility function that accounts for terrain traversability, obstacle proximity, objects of interest, and depth-based exploration reward. Sampled waypoints are projected into 3D and ordered through a real-time Traveling Salesman Problem (TSP) formulation, enabling receding-horizon goal selection. To address real-world navigation uncertainty, the framework introduces mechanisms, including temporary taboo regions to handle navigation failures and a graph-based relocation strategy for efficient backtracking across explored areas. We evaluate SGE in standardized simulation benchmarks against state-of-the-art exploration planners and demonstrate competitive performance in volumetric coverage, while enabling semantic task biasing that cannot be achieved by purely geometric methods. The framework is further validated through real-world experiments using multiple robotic platforms in indoor campus buildings and in limestone and coal mines. Results show consistent performance and adaptability across platforms and domains.

0.41

Implicit Additively Weighted Geodesic Voronoi Diagrams and Applications

cs.CG cs.DS ·2026-10-30 ·Bruce W. Brewer, Haitao Wang
top venue similarity 0.59
Abstract · To appear in SODA 2027

Let $P$ be a simple polygon with $m$ vertices. After $O(m)$-time preprocessing of $P$, for any set $S$ of $n$ additively weighted point sites, we compute an implicit additively weighted geodesic Voronoi diagram in $O(n\log n+n\log^2 m)$ time, supporting nearest-neighbor queries in $O(\log(n+m))$ time. In contrast, explicitly constructing the diagram requires $Ω(m)$ time. Our algorithm introduces a new sweep-line paradigm that avoids explicitly constructing the diagram, together with a novel technique for point location in implicit subdivisions. As applications, we obtain new dynamic data structures for additively weighted geodesic nearest-neighbor searching and the first efficient algorithms for shortest paths in geodesic disk graphs. After the same $O(m)$-time preprocessing, single-source shortest paths in a geodesic disk graph of $n$ sites can be computed in $O(n\log n+n\log^2 m)$ time in the unweighted case and $O(n^{3/2}(\log n+\log^2 m))$ time in the weighted case. We also extend our techniques to implicit farthest geodesic Voronoi diagrams for unweighted sites, obtaining analogous bounds and dynamic farthest-neighbor data structures.

0.47

ProTrav: Probabilistic Traversability with Elevation Uncertainty Propagation for Risk-aware Off-road Navigation

cs.RO ·2026-10-22 ·Chuanlin Zuo, Miloš Prágr, Arun Kumar Singh, Mohammad Loni, Reza Ghabcheloo
similarity 0.57
Abstract · 9 pages, 7 figures

Reliable traversability estimation is essential for autonomous navigation on unstructured terrain. State-of-the-art approaches typically evaluate traversability from deterministic terrain elevation, thereby overlooking spatial correlations in the terrain and failing to account for how elevation uncertainty propagates through nonlinear traversability mappings. We propose ProTrav, a probabilistic terrain representation that uses function-space sampling to generate spatially correlated terrain realizations and propagate elevation uncertainty to traversability cost. First, a Sparse Variational Gaussian Process (SVGP) reconstructs a probabilistic elevation field from observations. Then, posterior function-space sampling generates spatially correlated terrain realizations, preserving spatial dependencies between neighboring locations while propagating elevation uncertainty through geometric features into traversability cost. Consequently, a distribution of traversability cost at arbitrary location is established, where the mean and standard deviation quantify the expected traversability cost and associated uncertainty, respectively. A risk term is defined by moment-based Upper Confidence Bound (UCB) and incorporated into a Model Predictive Path Integral (MPPI) controller for risk-aware navigation. Simulation experiments demonstrate navigation success rates exceeding 90\% on different terrains, compared with below 40\% for a baseline, while reducing attitude variations. Furthermore, the proposed approach is validated on a robot traversing real-world off-road terrain.

0.13

Neural Centroidal Voronoi Tessellations

cs.GR ·2026-09-08 ·Jiacheng Xu, Bo Pang, Rui Xu, Xiaocheng Zhang, Yang Liu +3 more
similarity 0.56
Abstract

Centroidal Voronoi tessellation (CVT) is a fundamental primitive for high-quality surface sampling and isotropic remeshing in computer graphics. However, computing surface CVTs with classical solvers remains expensive: each optimization step repeatedly constructs restricted Voronoi diagrams (RVDs) and integrates quantities over their surface cells. We introduce Neural CVT, a learning-based surface-CVT solver that replaces these costly geometric computations with a recurrent neural optimizer, accelerating CVT optimization by one to two orders of magnitude in our benchmarks while preserving geometric fidelity. Given an input surface, we sample a dense point cloud and extract multi-scale geometric descriptors with a graph neural encoder. A lightweight recurrent optimizer then refines seed positions over a small number of iterations, aggregating interpolated surface features and optimization history to predict per-seed displacements. The framework is trained self-supervised using CVT objectives that promote uniform distributions and, when desired, feature alignment. Across diverse organic and CAD-like shapes, Neural CVT generalizes to unseen geometry, initialization strategies, and seed densities, producing isotropic, feature-preserving remeshes comparable to state-of-the-art offline optimization methods at a fraction of the computational cost. Code and trained models will be released.

0.25

GPU-accelerated Incremental Euclidean Distance Transform for Online Motion Planning of Mobile Robots

cs.RO ·2026-10-30 ·Yizhou Chen, Shupeng Lai, Jinqiang Cui, Biao Wang, Ben M. Chen
top venuecode/datahighly cited similarity 0.56
Abstract · Published in RA-L 2022. Author-accepted manuscript. Code: https://github.com/JINXER000/GIE-mapping

In this letter, we present a volumetric mapping system that effectively calculates Occupancy Grid Maps (OGMs) and Euclidean Distance Transforms (EDTs) with parallel computing. Unlike these mappers for high-precision structural reconstruction, our system incrementally constructs global EDT and outputs high-frequency local distance information for online robot motion planning. The proposed system constructs OGM with massive amount of data from multiple types of sensor inputs. Using GPU programming techniques, the system quickly computes EDT in parallel within local volume. The new observation is continuously integrated into the global EDT using the parallel wavefront algorithm while preserving the historical observations. Experiments with datasets have shown that our proposed approach outperforms existing state-of-the-art robot mapping systems and is particularly suitable for mapping unexplored areas. In its actual implementations on aerial and ground vehicles, the proposed system achieves real-time performance with limited onboard computational resources.

0.87

Pheno-GS: Phenoscape-scale Geodesic Sinkhorn

cs.LG q-bio.QM ·2026-09-23 ·Alistair Wilkinson, Christopher J. Tape, Smita Krishnaswamy
published similarity 0.55
Abstract · Camera-ready version accepted at IEEE MLSP 2026; notation corrections to mathematical typesetting

High-throughput single-cell data is now collected across large patient cohorts. Understanding patient-level heterogeneity from cellular-level data motivates phenoscaping: embedding each single-cell distribution as a "datapoint," with distances given by optimal transport (OT). Computing geometry-aware OT at this scale, between all pairs of patient datasets, remains an open challenge, since existing methods either rely on Euclidean ground metrics that distort manifold structure or fail under sparse, unevenly sampled, or large-scale data. We present \textbf{Pheno-GS} (Phenoscape-scale Geodesic Sinkhorn), which computes accurate, scalable geodesic transport distances under noisy, unbalanced, large-scale settings via three components: ($1$) graph connectivity regularization for well-defined geodesics on sparse/disconnected manifolds; ($2$) an unbalanced OT formulation via KL marginal penalties; and ($3$) a batched matrix algorithm computing all pairwise distances in one heat diffusion (over $200 \times$ faster than Geodesic Sinkhorn for $500$ distributions). We validate Pheno-GS on synthetic benchmarks and a CyTOF perturbation dataset.

0.35

Geometric Queries on Tessellation-Free Displaced Surfaces

cs.GR ·2026-10-15 ·Bing Xu, Yang Zhou, Brian Budge
similarity 0.55
Abstract

Displacement maps encode fine geometric detail in compact textures and simplify surface authoring, but using them typically requires pre-tessellating surfaces into dense triangle meshes, incurring a heavy memory cost. Recent tessellation-free methods enable direct ray tracing. However, broader geometric queries such as surface sampling, specular manifold search, and closest-point queries remain less explored. Supporting these operations requires surface enclosures, area estimates, and normal bounds, which scalar height intervals alone do not fully provide. We present a first-order texture-space hierarchy that unlocks these queries directly without pre-tessellation. Each node stores a local affine height plane and a conservative residual bound, retaining spatial height variation that scalar minimum--maximum bounds discard. The plane and residual provide surface enclosures for intersection and distance searches, while the plane's height and slopes supply area estimates for sampling. Additional slope bounds support specular light-path search. Building on this representation, we develop query-specific traversal, pruning, and sampling algorithms, and demonstrate them in caustics rendering, sampling displaced emitters, and surface partial differential equation (PDE) solvers. We demonstrate memory savings over pre-tessellation and performance improvements over query-specific baselines, while retaining efficient ray tracing.

0.17

CVTSplat: Multi-view Reconstruction Using an Adaptive Centroidal Voronoi Tessellation

cs.CV cs.GR ·2026-10-26 ·Briac Toussaint, Diego Thomas, Jean-Sébastien Franco, Edmond Boyer, Christian Theobalt
similarity 0.55
Abstract · 13 pages

Voronoi tessellations have recently emerged as an adaptive, space-partitioning discretization for shape and appearance reconstruction from multi-view images. However, the irregular cells they produce make the repeated reconstruction of the tessellation during optimization costly. We therefore explore adaptive centroidal Voronoi tessellations (CVTs), which extend standard CVTs with non-uniform cell sizes while preserving the regular, well-shaped cells that make them efficient to compute. In CVTSplat, cell size is modulated by the evolving signed distance field, concentrating sites near the zero level set while keeping cells nearly centroidal. This regularity lets us specialize the whole pipeline, with GPU algorithms for nearest-neighbor queries and approximate Voronoi construction, and a rasterizer tailored to small, nearly isotropic cells. Our Voronoi construction is 5 to 10 times faster than general-purpose alternatives in this regime. On DTU and BlendedMVS, CVTSplat reaches geometric accuracy competitive with the best Gaussian-splatting surface methods while training in about 2.5 minutes on a single GPU.

0.26