map software developers

Abstract: Vector tiles are delivered as pyramids of small, independently encoded units, whose spatial granularity is largely determined by the tiling scheme. We investigate how this granularity affects compression in column-oriented MapLibre Tiles (MLT), using feature-oriented Mapbox Vector Tiles (MVT) as a baseline. Five heterogeneous geospatial datasets were encoded as conventional tile pyramids and as two denser variants grouping the area of 2 x 2 or 4 x 4 conventional tiles into one encoding unit at approximately matched logical levels of detail. Compared with conventional tiling, the 4 x 4 variant increased MLT's raw size saving over MVT by 1.0-7.3 percentage points across all five datasets. After per-tile gzip, the saving increased by 1.5-6.4 points in four datasets and decreased by 1.4 points in one. Coarser granularity lengthened MLT streams and reduced structural overhead in every dataset. The largest raw gains occurred where conventional tiles had the shortest streams: as mean values per stream rose from 27 to 2,075 across datasets, the raw gain decreased from 7.3 to 1.0 points. Encoded payload bytes per value also declined, with the strongest reductions in two datasets. For the two sparse datasets, coarser units reduced bytes per vertex across both formats, with or without gzip; the resulting 4 x 4 MLT+gzip archives were 71% and 33% smaller than the conventional ones. Thus, the measured compression advantage of MLT depends on spatial encoding-unit granularity, and conventional fine-grained tiling can understate the potential of column-oriented compression.

Abstract: This paper addresses the following problem: given a planar embedding graph, compute a representation of the shortest-path trees rooted at all the boundary nodes of the graph. Klein gave an $O(n \log n)$ algorithm for this problem; the algorithm subsequently became an essential ingredient in dozens of algorithms, addressing problems ranging from distance oracles to edit distance. However, the correctness and analysis in that original paper is complicated and messy and hard to understand. In this paper, we give a simple and clear analysis.

Abstract: Given a directed graph with positive edge weights and two vertices s,t, a next-to-shortest s-t path is a shortest simple s-t path among those whose length is strictly larger than the shortest-path distance. The problem was introduced by Lalgudi, Papaefthymiou and Potkonjak in 1996; it is NP-hard when zero-weight edges are allowed, and its complexity on positively weighted digraphs remained open for almost three decades until Chen, Wein and Zhang recently gave a polynomial-time algorithm running in O(n^4 m^3 log n) time. We give a substantially faster algorithm within their optimal-middle-segment framework. The core idea is to split the problem into "choosing a prefix" and "completing it". Given a prefix P: s -> A made of shortest-path edges, delete the vertices used by P, forbid leaving A along shortest-path edges, and the best completion is one shortest-path computation. The difficulty lies in choosing P: even for a fixed A, deciding whether some shortest prefix admits a completion is NP-complete. We do not solve these fixed-A subproblems one by one. Fix any globally optimal next-to-shortest path; its middle segment induces a boundary edge x -> c in the shortest-path DAG. For the correct triple (A,B,x), the optimal path certifies c as a feasible next hop, and we prove that every feasible next hop that is not earlier than c in a topological order can be combined with the same middle segment into another globally optimal path. Hence only the feasible next hop of maximum topological index is kept per triple, giving O(n^3) representatives, all generated by a two-dimensional DAG dynamic program with a local reward. The total running time is O(n^3 (m + n log n)), and O(n^3 m) on unweighted graphs. The proof rests on an uncrossing lemma: the last intersection between a reference prefix and the candidate's partner suffix can always be moved strictly earlier, which cannot go on forever.