CS Paper Radar

Linear-Time Transformations Between Connectivity Maintenance and Points Spreading on Linear and Cyclic Domains

Nicolás Honorato-Droguett

cs.CG ·submitted 2026-08-23 04:46 UTC · v1

Abstract

Given $n$ points on a line or closed cycle and a threshold $r>0$, the connectivity-maintenance problem is to move the points so that every gap between consecutive points is at most $r$, whereas the points-spreading problem requires every gap to be at least $r$. Li and Wang [CCCG 2015; CGT 2025] and Chen, Gu, Li, and Wang [SWAT 2012; DCG 2013] gave $O(n)$-time algorithms for the cyclic versions of min-max points-spreading and min-max connectivity-maintenance, respectively. Ghadiri and Yazdanbod [CCCG 2016] gave an $O(n\log n)$-time algorithm for the linear version of min-sum points-spreading. In this paper, we show that the two problems can be reduced in linear time to each other for both objectives and on both linear and cyclic domains. As an implication, min-sum connectivity-maintenance is solvable in $O(n\log n)$ time on both domains. Finally, we extend the reduction to points on a line with individual thresholds when their initial order is preserved.

Closest papers

Nearest neighbours by meaning across the whole index.

A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane

cs.CG ·2026-09-08 ·Sarita de Berg, Jacobus Conradi, Peter Kramer, André Nusser, Sampson Wong
similarity 0.62
Abstract · 46 pages, 18 figures

The dilation of a geometric graph measures how much longer the path between pairs of points becomes when restricted to graph edges, rather than following the direct path through the ambient space. The minimum dilation tree of a point set is the spanning tree with minimum dilation, where edge lengths in the tree are given by distances in the ambient space. In the Euclidean plane, computing the minimum dilation tree is NP-hard, but no hardness of approximation result is known. On the other hand, the minimum spanning tree is an $(n-1)$-approximation to the minimum dilation tree, but no asymptotically-better approximation algorithm is known for general point sets in the Euclidean plane. We give the first sublinear approximation algorithm for the minimum dilation tree in the Euclidean plane. Our approximation ratio is $\tilde{O}(n^{14/15})$ and our algorithm runs in polynomial time. This resolves an open problem proposed by Eppstein in 1996.

0.32

Polynomial-time algorithm for exact $(1,2)$-center problem under continuous Fréchet distance

cs.CG cs.DS ·2026-09-30 ·Soumya Bhattacharya, Serene Rasheed, Sasanka Roy
similarity 0.61
Abstract

In this paper, we explore the $(1,2)$-center problem for polygonal curves under continuous Fréchet distance. The $(k,\ell)$-center problem, in general, is known to be NP-hard. Aronov, Filtser, Horton, Katz, and Sheikhan (WADS'19) gave a polynomial-time algorithm for the $(1,2)$-center of curves in the plane under the discrete Fréchet distance. To the best of our knowledge, the $(1,2)$-center under continuous Fréchet distance has not been studied yet. We present a polynomial time algorithm to solve the problem exactly under both $\mathbb{L}_2$ and $\mathbb{L}_\infty$ norm, running in $O\bigr((n^2r+nr^2)^{2+ε}\bigl)$ time for curves in the plane where $r$ is the number of input curves and $n$ is the maximum complexity of any curve. Further, for curves in any dimension $d$, the expected time to compute the center using the algorithm is $O\bigr((n^2r+nr^2)^{2(d-1)+ε}\bigl)$. We have also shown that an $(1+\widetildeε)-$factor approximation of $(1,2)$-center can be computed in $O(n^2r+nr^2+1/ε^s)$ time for any $ε>\widetildeε>0$ and some constant $s$ for curves in the plane. For curves in the plane, we have shown that, with the center restricted to be horizontal, we can compute the exact center in $O(n^2r+nr^2)$ time. An algorithm has been introduced to find a $3$-factor approximation of the $(1,2)$-center in time linear in the number of curves. A formulation was introduced by de Berg, Mehrabi, and Ophelders (CCCG'17) to measure Fréchet distance between a curve and a query segment under $\mathbb{L}_2$ norm for curves in the plane. We have shown the formulation is valid under both $\mathbb{L}_2$ and $\mathbb{L}_\infty$ norm for curves in $\mathbb{R}^d$.

0.22

Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time

cs.DS ·2026-09-30 ·Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh
top venue similarity 0.60
Abstract · To appear in FOCS 2026

We give fully dynamic algorithms for maintaining connectivity, minimum spanning tree, and $2$-edge connectivity of a graph with worst-case polylogarithmic update time. Our algorithms are randomized and succeed with high probability against an adaptive adversary. For the minimum spanning tree and $2$-edge connectivity problems, this improves over the subpolynomial update time bounds obtained by Nanongkai, Saranurak, and Wulff-Nilsen [FOCS'17], Jin and Sun [FOCS'21], and Jin, Sun, and Thorup [SODA'24], respectively. The only randomized component of our algorithms is the computation of static expander decompositions, and a deterministic algorithm for said problem would directly imply deterministic algorithms for all three problems. This reduction is novel even for the connectivity problem.

0.24

Dynamic Steiner Tree under Edge Updates

cs.DS ·2026-11-03 ·Jeff Giliberti, MohammadTaghi Hajiaghayi, Mohammad Mahdavi, Xinchen Yang
hot direction similarity 0.59
Abstract

The Steiner tree problem is the canonical generalization of minimum spanning tree (MST). When connectivity is required only among a fixed subset of vertices (terminals), the goal is to maintain a minimum-cost tree connecting these terminals as the graph undergoes edge updates. While dynamic MST has been studied since the 1980s~[Frederickson, STOC'83, SICOMP'85], and the first sublinear-in-$n$ dynamic MST algorithm dates back almost thirty-five years to Eppstein, Galil, Italiano, and Nissenzweig~[FOCS'92, JACM'97], achieving sublinear-in-$n$ update time for dynamic Steiner tree has long remained open, as a single edge update can invalidate many routes in the underlying terminal metric closure. We present the first fully dynamic algorithm for Steiner tree that achieves a constant-factor approximation with sublinear-in-$n$ update time. For any fixed $0<ζ<1/2$, our deterministic algorithm maintains an $O_ζ(1)$-approximate Steiner tree for undirected graphs with polynomially bounded edge weights in $\widetilde O(n^{1/2+ζ})$ amortized update time, answering cost queries in $O(1)$ time, and reporting an explicit tree in $\widetilde O(n^{1+ζ})$ time. Our approach combines periodic terminal-metric rebuilds on a dynamic spanner with a top-tree dynamic program that localizes edge deletions and reconnects surviving components through a dynamic distance sparsifier. Along the way, we give a simpler randomized insertion-only algorithm with a better, explicit approximation ratio.

0.25

Optimal Planar $k$ Nearest Neighbors Queries for Additively Weighted Euclidean Distances and Convex Metrics

cs.CG ·2026-10-12 ·Chih-Hung Liu
top venuetheory similarity 0.59
Abstract · 78 pages. A conference version will appear in the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)

Given a set $P$ of $n$ point sites in the plane, the $k$ nearest neighbors problem is to build a data structure that, for a query point $v$ and a query integer $k$, reports the $k$ nearest point sites of $v$ in $P$ efficiently. For the Euclidean metric, after four decades of efforts, an optimal data structure has been developed with $O(n)$ space, $O(\log n+k)$ query time and $O(n\log n)$ preprocessing time [Mat92b, Cha00, AC09, CT16]. In contrast, for a family of distance functions, the state-of-the-art data structure [AES99, KMR+20, Liu22] attains $O(n\log\log n)$ space, $O(\log n+k)$ query time and expected $O(n\log n)$ preprocessing time. An open question is the existence of an optimal data structure with $O(n)$ space and $O(\log n + k)$ query time for distance functions more general than the Euclidean metric. Such an optimal data structure also remains unknown for non-point sites in the Euclidean metric, even for disk sites or, more generally, additively weighted Euclidean distances. We develop an optimal $k$-nearest-neighbors data structure for additively weighted Euclidean distances with $O(n)$ space, $O(\log n + k)$ query time and expected $O(n\log n)$ preprocessing time. Since this data structure can be adjusted to disk sites, it serves as an initial result toward optimality for non-point sites. We also adapt our data structure to point sites under a family of convex metrics, including commonly used $L_p$ metrics and uniform orientation metrics. The data structure can be further extended to distance functions that satisfy certain axioms. Thus, we demonstrate the existence of optimal $k$-nearest-neighbors data structures for distance functions more general than point sites in the Euclidean metric. Our main technical advance is to generalize Matoušek's shallow partition theorem for hyperplanes [Mat92b] to these settings, while achieving a logarithmic crossing number.

0.42

When Shall We $k$ Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance

cs.DS ·2026-09-18 ·Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova, Virginia Vassilevska Williams
theory similarity 0.59
Abstract · 20 pages

Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computational geometry. In this work, we use the two objectives of optimal meeting points examined in the literature to study two notions of meet-distance: $d^{\max}(u,v)$, the minimum over all meeting points $w$ of $\max(d(u,w), d(v,w))$; and $d^+(u,v)$, the minimum over all meeting points of $d(u,w) + d(v,w)$. These values measure the minimum time and minimum total distance required for two agents to meet. We initiate the fine-grained study of fundamental graph parameters under the two notions of meet-distance, namely the diameter, radius and eccentricities. For general directed graphs, we give an $\tilde{O}(m\sqrt{n})$ time algorithm for computing a 2-approximation to both notions of meet-diameter and show that this result is optimal under SETH. In contrast, we show that such a result is unattainable for the meet-radius as any finite approximation requires quadratic time under the Hitting Set Conjecture. For directed acyclic graphs, we obtain stronger results. We compute the meet$^{\max}$-diameter exactly in linear time and give a linear-time $2$-approximation for the meet$^{+}$-diameter. We complement the latter with a quadratic-time lower bound for any $(3/2-\varepsilon)$-approximation under SETH, yielding a separation between the two meet-distance objectives. Finally, we study the generalized meet-distance of $k$-tuples of vertices. For every positive integer $\ell$, we reduce the problem of $\ell$-approximating the $k$-point meet-diameter to computing an exact meet-diameter on smaller tuples, obtaining an $\ell$-approximation in time \[ O\!\left( mn+ \ell \left\lceil k^{1/\ell}\right\rceil n^{\left\lceil k^{1/\ell}\right\rceil+1} \right). \]

0.28

A polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in fixed dimension

cs.DS math.CO ·2026-11-11 ·Daniel Skachkov, Yuriy Dorn
similarity 0.58
Abstract

In the Traveling Salesman Problem, a route must visit all customers and return to its starting point while minimizing its total length. The Minimum Latency Problem, also known as the Traveling Repairman Problem, instead minimizes the sum of the times at which customers are first visited. We give a deterministic polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in every fixed dimension, with arbitrary nonnegative customer weights. Our proof restricts the form of a solution in three steps, each with a controlled increase in cost. First, a decomposition based on Sitters' method assigns customers to phases that start and end at the root. Second, within each phase, we divide the route into a constant number of blocks and charge each customer at the end of its assigned block. The resulting objective is a nonnegative linear combination of block lengths. Third, we add an auxiliary dimension and use a fixed Minkowski norm to close each block path into a tour. Arora's closed-tour estimate then gives paths that cross the boundaries of a common dissection only at designated portals and a bounded number of times per face. A dynamic program optimizes the restricted objective, and projecting its paths back to the original space gives the final route. Rounding weights and coordinates keeps the state space polynomial.

0.30

A PTAS for Euclidean Capacitated Vehicle Routing

cs.DS ·2026-11-13 ·Zachary Friggstad, Fabrizio Grandoni, Ramin Mousavi, Kinter Ren, Mohammad R. Salavatipour
top venuehot direction similarity 0.58
Abstract

In the Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959, we are given an $n$-node graph $G=(V,E)$ with metric edges costs $c(e)$, a depot $r\in V$, and an integer vehicle capacity $Q$. The goal is to find a minimum-cost collection of tours, each containing the depot and visiting at most other $Q$ nodes, such that the tours cover all the nodes. In this paper we focus on the Euclidean CVRP problem, where the nodes represent points on $\mathbb{R}^2$, and the edge costs are the respective Euclidean distances. Euclidean CVRP generalizes the classical NP-hard Euclidean TSP problem (the special case with $Q=n-1$), that admits a PTAS [Arora FOCS'96/Mitchell SODA'96]. A long-standing open problem has been generalizing the latter PTAS to Euclidean CVRP. A polynomial-time $(2+ε)$-approximation for this problem follows from the PTAS for Euclidean TSP and the tour-partitioning technique for CVRP [Haimovich, Kan Math. OR'85]. This was the best known until a recent improvement of the approximation factor to slightly below 2 [Friggstad, Grandoni, Mousavi SODA'26]. There have been a series of papers presenting improved QPTASs by Das and Mathieu [SODA'10] (time $n^{\log^{O(1/ε)}n}$), Jayaprakash and Salavatipour [SODA'22] (time $n^{O_ε(\log^6 n)}$), and recently Sitters [ArXiV'25] (time $n^{O_ε(\log\log n)}$). In this paper, we solve the mentioned long-standing open problem by presenting a PTAS for Euclidean CVRP.

0.46