mapping software engineers

Abstract: Given n points and $ε>0$, a well-separated pair decomposition (WSPD) is a collection of dumbbells {X,Y}, where X and Y have diameter at most $ε$ times their distance, such that every pair of points has one point in X and the other in Y for some dumbbell. A partition WSPD covers every pair exactly once, and a cover WSPD at least once. Callahan and Kosaraju give a partition WSPD with $O(n/ε^d)$ dumbbells in $R^d$, but many point sets have far smaller WSPDs of both kinds. For $d\ge2$, the known $O(1)$-approximations of the minimum size WSPD that preserve the separation $ε$ have unspecified factors, above $10^7$ for $d=2$ by our estimates. For cover WSPDs, we give an $O(n^2\log n)$-time sweep approximation algorithm with a factor 40 in the plane for $ε\le1/16$. It extends to $R^d$ with a factor $2^{O(d)}$. The sweep is also a lower-bound tool: its number of steps is a lower bound on the WSPD size. For partition WSPDs, we analyze quadtree and fair split tree constructions: in the plane and for $ε\le1/5$, they give constant approximation factors, the smallest of which is 252 for a randomly shifted and scaled quadtree. In experiments with $ε=1/20$, the number of sweep steps is at least 0.91 OPT for n = 500, where the optimum OPT is known, and a local search raises it to a lower bound of 0.99 OPT. A greedy variant of the sweep, which is still a certified 40-approximation, is at most 1.28 times the lower bound for n = 10000. Followed by a new local-search heuristic that shrinks the WSPD, it is within 0.02% of the optimum on every instance with n = 500, and at most 1.10 times the lower bound for n = 10000. We then show how to convert the cover WSPDs into partition WSPDs. For n = 10000, the conversion gives on average 1.13 times the lower bound, against 1.05 for the cover WSPD itself and 1.55 for the Callahan-Kosaraju partition WSPD.

Abstract: Aerial map matching provides position observations for navigation, but a position error alone does not determine how an observation should be weighted. We define five benchmark tasks: position availability and agreement, grouped error structure, predictive uncertainty, controlled updates, and temporal accumulation. A case study in digital-surface-model-assisted localization evaluates base-anchored uncertainty calibration within this framework. The method combines propagated image and map sensitivities with the second moment of a compact configuration subset relative to the reported position. The reported position remains unchanged, and scale is fitted using separate position references without local surface-height ground truth. Thirteen covariance models are evaluated on two held-out query sets from locations represented in the calibration data. Relative to a constant full-matrix baseline, the method reduces equal-location normalized position-update risk by 7.70% on 728 conditions and 5.46% on a separate 142 conditions under an independent prior, with all localization failures included. On the primary set, equal-location negative log likelihood improves by 2.571 nat. These results show improved reference-based weighting at seen locations. Exploratory base-quality and conditional-addition controls leave the incremental update benefit of configuration disagreement unresolved. Navigation benefit and real temporal accumulation remain untested.

Abstract: Large-scale vectorized HD maps provide structured road information that is essential for perception, localization, and planning in autonomous driving. Constructing such maps requires aggregating noisy, fragmented, and overlapping local predictions collected along a vehicle trajectory into a coherent global map. Existing aggregation methods typically rely on hand-crafted rules for fragment association and refinement. However, a fixed set of thresholds cannot effectively handle variations in road structures and prediction errors, often requiring detector-specific tuning or manual adjustment. To address this limitation, we propose MapMergeLLM, a data-driven framework that formulates vectorized map aggregation as conditional sequence generation with a large language model. Given serialized local vectorized maps, our model directly predicts the aggregated global map polylines. To reduce dependence on any particular upstream detector, we train the model on synthetic local maps generated from clean vector maps using corruptions that simulate representative prediction errors. We further introduce a coordinate tokenizer with geometry-aware pretraining to precisely represent map coordinates. In addition, we propose a line-level association loss that explicitly supervises correspondences between local observations of the same map element. Experiments on Argoverse2 and nuScenes using multiple recent upstream detectors demonstrate that MapMergeLLM substantially outperforms heuristic and optimization-based aggregation baselines without detector-specific retraining.

Abstract: Vector polygon generation converts visual inputs, e.g., remote sensing (RS) images, into vectorized polygonal geometries, supporting applications such as autonomous driving, vector map construction, and remote sensing. Early pipelines predict raster masks and post-process them into polygons, which prevents end-to-end optimization and may miss small objects or introduce inaccurate vertices. Recent methods directly generate vector polygons, but most focus on simple exterior contours, while they either cannot represent complex polygons with holes or fail to preserve their topology. In this paper, we propose PolyTopoBench, a unified evaluation framework for vector polygon generation from RS images with explicit emphasis on complex polygons. PolyTopoBench evaluates both exterior and interior rings, and benchmarks 11 representative methods, including segmentation-based polygonization pipelines, vision foundation model baselines, and specialized vector polygon generators, on two RS-image datasets covering buildings, roads, vegetation, and unvegetated regions. Experiments show that existing methods often recover simple exterior boundaries but degrade substantially on polygons with holes or multiple rings. These results reveal complex polygon generation as an unresolved challenge and motivate topology-aware benchmarks and model designs. Code and data are available at https://github.com/seai-lab/PolyTopoBench.