ToPos: Automated Optimal Positioning on Topographic Manifolds using Constrained Geodesic Voronoi Decomposition
Authors: Rajesh Raveendran, Akseli Vanhamaa, Jaakko Suutala, Antti Tikanmäki, Juha Röning
Organizations: Faculty of Information Technology and Electrical Engineering, Biomimetics and Intelligent Systems Group (BISG), University of Oulu, Pentti Kaiteran katu 1, 90570 Oulu, Finland · Master’s student in Computer Science and Engineering, University of Oulu, Pentti Kaiteran katu 1, 90570 Oulu, Finland
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 ∼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.
Figures & tables
Fig. 1: Visualizing the Metric Distortion Gap and the ToPos solution. (Left) The planimetric 2D baseline fails to account for topographic relief, leading to spatial clustering and sparse coverage on steep slopes. (Right) The proposed ToPos framework achieves an optimal area-balanced distribution by optimizing directly on the manifold, ensuring uniform sampling density across high-relief terrain.
Feature
2D Euclidean Partitioning
ToPos (Ours)
Manifold Space
Planar Euclidean ( R2 )
Non-Euclidean 2-Manifold ( M )
Distance Metric
L2 Norm (Straight-line distance)
Intrinsic Geodesic Metric ( dg )
Area Measure
Planar Footprint Area
Topographic Surface Area element ( dA )
Optimization Logic
Standard Lloyd’s Iteration
Riemannian Nesterov Accelerated Gradient (NAG)
Spatial Distribution
Spatial Clustering in High-Relief Zones
Surface Area-Balanced Distribution Across the Manifold
TABLE I: Comparison Between Standard 2D Euclidean Partitioning and the Proposed ToPos Framework
Fig. 2: Visualization of the Heat Method on the benchmark topographic manifold M . The white Eikonal isolines represent equidistant geodesic contours emanating from a central Spatial Reference Site (white sphere). Note how the isolines deform to follow the intrinsic 3D curvature, providing the smooth, differentiable gradients required for ToPos optimization engine and voronoi decomposition.
Fig. 3: Visualizing the Riemannian Operators on the topographic manifold. The Logarithm map logz pulls the 3D geodesic error into the local Euclidean tangent space TzkM , while the Exponential map expz (realized as a retraction) maps the update vector v back onto the surface.
Fig. 4: The ToPos Graphical User Interface (GUI) demonstrating the integration of Manifold-Aware optimization with a standard GIS workflow. The interface highlights the Base Area (blue), Operational Voids (red regions, topologically carved out), and Non-Traversable Zones (purple regions, soft metric constraints). Note how the Spatial Reference Sites (red circles) are optimized to balance the surface area while strictly respecting the feasible boundary F .
Fig. 5: Visualization of the ToPos experimental environment. The 16,900-vertex sinusoidal manifold is augmented with hard manifold constraints with generators(green spheres), including an Operational Void (red region) and a Non-Traversable Zone (blue region). Note how the Geodesic Voronoi Cells adapt to the topographic relief, ensuring that no generators ( n = 100) are placed within the forbidden zones.
n
Algorithm
Mean CV
Std dev ( σ )
Time/Step
10
Lloyd (Standard)
0.4953
0.1643
79.8 ms
Adapt. Area-Balanced
0.2152
0.0597
78.9 ms
Riem. Momentum
0.1426
0.0176
79.4 ms
ToPos (Proposed)
0.1541
0.0162
81.9 ms
50
Lloyd (Standard)
0.5396
0.0528
364.2 ms
Adapt. Area-Balanced
0.2750
0.0318
365.3 ms
TABLE II: Quantitative Benchmarking Results across Generator Densities (100 Iterations)
Fig. 6: Convergence analysis ( n = 100 Generators)
Fig. 7: Geometric stability across generator densities
Fig. 8: Computational efficiency analysis by comparing execution time across generator densities
Surface manipulation tasks require robots to generate trajectories that comprehensively cover complex 3D surfaces while maintaining precise end-effector poses. Existing ergodic trajectory optimization (TO) methods demonstrate success in coverage tasks, while struggling with point-cloud targets due to the nonconvex optimization landscapes and the inadequate handling of SE(3) constraints in sampling-as-optimization (SAO) techniques. In this work, we introduce a preconditioned SE(3) Stein Variational Gradient Descent (SVGD) approach for SAO ergodic trajectory generation. Our proposed approach comprises multiple innovations. First, we reformulate point-cloud ergodic coverage as a manifold-aware sampling problem. Second, we derive SE(3)-specific SVGD particle updates, and, third, we develop a preconditioner to accelerate TO convergence. Our sampling-based framework consistently identifies superior local optima compared to strong optimization-based and SAO baselines while preserving the SE(3) geometric structure. Experiments on a 3D point-cloud surface coverage benchmark and robotic surface drawing tasks demonstrate that our method achieves superior coverage quality with tractable computation in our setting relative to existing TO and SAO approaches, and is validated in real-world robot experiments.
Jiayun Li, Yufeng Jin, Sangli Teng +2
Department of Computer Science, TU Darmstadt, Darmstadt, Germany. · Hessian.AI, Darmstadt, Germany. · Honda Research Institute Europe GmbH, Offenbach, Germany. +1
Planning motions that respect the intrinsic geometry of a robot's configuration space, including its curvature and a configuration-dependent notion of cost, yields shorter, lower-energy, and more natural trajectories than planning under the ambient flat metric. Existing libraries for optimization on manifolds provide rich geometric primitives but do not plan around obstacles. While general-purpose motion planning libraries support many state spaces and custom distance functions, they do not yet treat a configuration-dependent Riemannian metric as the geometry that drives distance, interpolation, and geodesics. We present geodex, an open-source C++20 library with Python bindings. The library exposes the manifold, its Riemannian metric, the retraction, and the sampler as independent, interchangeable components through a single sampling-based motion planning interface. The same planner runs unchanged on canonical spaces Rn, Tn, Sn, matrix Lie groups such as SO(2), SE(2), SO(3), and SE(3), products of these spaces, and articulated-robot configuration spaces, each equipped with a user-defined Riemannian metric. We make geodex publicly available with documentation, tests, and a reproducible benchmark suite.
Phone Thiha Kyaw, Ben Wei, Sepehr Samavi +2
Space & Terrestrial Autonomous Robotic Systems (STARS) Laboratory at the University of Toronto Institute for Aerospace Studies (UTIAS), Toronto, Ontario, Canada, M3H 5T6
Real-time 3D mapping is fundamental for autonomous robotic navigation, with Euclidean Signed Distance Fields (ESDFs) serving as the standard representation for online motion planning. While recent advancements in non- projective distance fields yield highly accurate maps, their computational overhead remains a severe bottleneck. Conventional integrators redundantly re-fuse millions of depth pixels every frame, even long after the corresponding voxels have converged, wasting significant computational resources in environments dominated by large planar surfaces. In this paper, we present SHIFT (Surface-aware High-speed Integration For TSDFs), an efficient mapping framework designed to reduce this per-frame update cost. By exploiting structural redundancy directly from 3D depth geometry, SHIFT compresses flat local regions into weighted super-rays and freezes flat-voxel gradients. A compact ESDF voxel layout further reduces the memory footprint of the remaining wavefront. Extensive evaluations across various RGB-D and LiDAR sequences show that SHIFT cuts TSDF cost by 1.42 to 4.07 times, while holding mesh error within millimeters, and reduces ESDF-layer memory by up to 28%
Ayaan Choudhury, Lokender Tiwari
Indian Institute of Technology Jodhpur · BotLab Dynamics