CS Paper Radar

The Stretch Factor of Planar Delaunay Triangulations Is Nearly Determined

Guanlin Mo, Kangke Cheng, Hu Ding

cs.CG ·submitted 2026-09-07 20:58 UTC · v6
theory

Abstract

The Delaunay triangulation is a classical geometric structure on a finite set of points in the plane. Its stretch factor is the largest ratio of the shortest-path distance along its edges to the Euclidean distance between the same two points. Determining the worst-case stretch factor of planar Delaunay triangulations is a long-standing open problem. We prove a uniform upper bound of 1.5949, improving the previous bound of 1.998 and narrowing the gap to the best known lower bound of 1.5932 from 0.4048 to less than 0.0017, nearly pinpointing the worst-case stretch factor. A central difficulty is that the line segment between two points may cross arbitrarily many triangles. Our progress accounting framework addresses this by converting the global bound into a family of local inequalities, each involving only a fixed number of real parameters regardless of the number of triangles crossed. Two further geometric lemmas make computer-assisted verification tractable: the pencil lemma decomposes each local transition into two geometrically independent stages, reducing verification over infinitely many possible next disks to a single differential condition; and the corner lemmas handle degenerate boundary cases where direct verification would fail. With these reductions, the proof ends with a finite verification of an explicit potential in exact rational arithmetic and outward-rounded interval arithmetic. Numerous geometric network constructions use the Delaunay stretch factor as a black box, so the tighter bound directly improves stretch-factor guarantees for a range of downstream applications, including bounded-degree plane spanners and low-weight spanners.

Comment
67 pages, 14 figures, 8 tables. Substantially revised: the upper bound is improved from 1.65 to 1.5949, and the title has changed. Verification data and code: https://doi.org/10.5281/zenodo.23835635

Closest papers

Nearest neighbours by meaning across the whole index.

Computing an e-net of a closed hyperbolic surface

cs.CG math.GT ·2026-08-25 ·Vincent Delecroix, Vincent Despré, Camille Lanuel, Hugo Parlier, Monique Teillaud
similarity 0.67
Abstract

Hyperbolic surfaces are a fundamental object in mathematics and play an increasingly important role in computational geometry and topology. A key ingredient in the design of efficient algorithms on such surfaces is the availability of a geometric discretization of controlled complexity. In this paper, we present the first algorithm for constructing e-nets on hyperbolic surfaces starting from a fundamental polygon representation. Our approach is based on Delaunay refinement and relies on maintaining Delaunay triangulations through edge flips. The size of an e-net cannot be bounded solely as a function of the genus because of the presence of arbitrarily long collars around short geodesics. To overcome this difficulty, we introduce the notion of a pseudo e-net, which decomposes the surface into e-thin cylinders together with a Delaunay triangulation over an e-net of the remaining thick part. As applications, we obtain algorithms for computing the length spectrum of an e-thick hyperbolic surface and for computing the systole from a pseudo log(sqrt(2))-net. These results demonstrate that Delaunay-based discretizations provide a practical and versatile framework for algorithmic computations on hyperbolic surfaces.

0.45

Quadratic Complexity of Voronoi Diagrams in $\mathbb{R}^3$ for Lines in a Single Ruling of a Regulus

cs.CG math.AG ·2026-08-27 ·Eunku Park, Kangjin Han
theory similarity 0.64
Abstract · Added a coauthor, more detailed explanations of algebraic geometry, and additional figures

We study nearest and farthest Voronoi diagrams of lines in three-dimensional Euclidean space, which partition space according to the closest and farthest input lines, respectively. For arbitrary lines, a gap remains between the known quadratic lower bound and near-cubic upper bounds for the complexity of the nearest diagram. We consider input lines chosen from one of two continuous families of straight lines on a smooth surface defined by a quadratic equation, with one line from each family passing through every point of the surface. Under the geometric assumptions stated in the paper, we prove quadratic upper bounds on the total number of vertices, edges, faces, and connected three-dimensional regions in both diagrams. We also construct quadratically many nearest vertices using lines from a single family on one fixed surface, establishing a tight quadratic worst-case bound. The farthest diagram has quadratic total complexity for every input satisfying our assumptions. Our proof uses a parametrization that arranges the input lines in a cyclic order and expresses tangency to a sphere by a polynomial equation of degree four. At a Voronoi vertex, the four tangent input lines give four distinct roots. The sign changes between these roots, together with the nearest or farthest condition, force two intervening parameter intervals to contain no other input parameters. Thus, only quadratically many choices of four lines can define a vertex, and each choice yields at most eight isolated candidate centers.

0.27

Triangle Covers of Polygons: Approximation Algorithms and Complexity

cs.CG ·2026-10-16 ·Linda Kleist, Lena Scherzer
similarity 0.63
Abstract · 37 pages, 32 figures, GeoGebra file

We study the geometric set cover problems of covering and partitioning a polygon into a minimum number of triangles. While the decision version of the covering problem is known to be APX-hard and $\exists\mathbb R$-complete (even for polygons without holes and vertices in general position), the computational complexity of partitioning a simple polygon into a minimum number of triangles is open. Our main result refutes a 40 year old conjecture by Asano, Asano, and Pinter stating that the triangle vertices of a minimum partition lie on intersection points of special lines, which are iteratively generated by the polygon vertices and the intersection points. In particular, we show that there exist polygons where all minimum triangle partitions need Steiner points with irrational coordinates. This indicates that the problem might be more complex than previously expected. Complementarily, we provide a simple constant factor approximation to compute a minimum triangle partition of a given polygon (possibly with holes). In the context of coverings, we devise the first constant factor approximation for computing a minimum triangle cover of a simple polygon. For general polygons, an $O(\log n)$-approximation follows by close inspection of previous work.

0.27

On the Spanning Ratio of the Greedy Triangulation for Convex Point Sets

cs.CG ·2026-08-10 ·Prosenjit Bose, Jean Lou de Carufel, Anil Maheshwari, Bobby Miraftab, Michiel Smid +1 more
theory similarity 0.61
Abstract

The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an earlier one. Its spanning ratio is known to be bounded by a universal constant, but the standard bound obtained from the diamond and good-polygon properties is about $11739.1$. We prove a substantially smaller bound for points in convex position. In particular, for every finite point set $P\subset\mathbb{R}^2$ in convex position and every pair $u,v\in P$, the greedy triangulation contains a $u$--$v$ path of length at most $κ|uv|$, where $κ<17.814$. Thus, the greedy triangulation of a convex point set is an $18$-spanner.

0.04

Parameter-Free Triangle Counting

cs.DS ·2026-09-21 ·Asaf Etgar, Anna Gilbert, Quanquan Liu, Andrew McGregor
theory similarity 0.60
Abstract

Given an undirected, unweighted graph $G = (V,E)$ with $n$ vertices and $m$ edges, the triangle counting problem seeks the number of three-cycles in it. Triangle and subgraph counting are classical problems in graph algorithms, central to applications such as community detection, computing the clustering coefficient, motif discovery in protein networks, and social network analysis. In many of these applications, the graph datasets are so voluminous that we model them as streams of updates to an underlying graph. There are a number of foundational results for streaming triangle counting, both theoretical and practical. There is, however, one major drawback to all previous sublinear-space algorithms: to achieve both a constant factor approximation and the sublinear space guarantees, one needs to know a priori a constant factor approximation of the triangle count $T$, an inherently circular requirement. We initiate the study of parameter-free streaming triangle counting, without any a priori knowledge of $T$ or any quantities depending on $T$, provided $m$, the length of the stream. We describe a family of $O(p)$ pass parameter-free triangle counting algorithms that guarantee a mixed multiplicative and additive approximation of $T$ and use $\widetilde{O}(\frac{m+T}{\sqrt{T}})$ expected space. Moreover, this family leads to an $O(\log\log(n))$ pass algorithm that gives a $(1+\eps)$ multiplicative approximation of $T$ with the same space complexity. These algorithms rely on the notion of a \emph{verified} parametrized algorithm: an algorithm parametrized by $τ$ that either provides an approximation of $T$ when $τ\le T$, or declares that $T < τ$. Furthermore, we prove a lower bound: any parameter-free algorithm that provides a multiplicative approximation for all values of $T$ must use $Θ(m)$ space, even on streams where the triangle count is moderately large.

0.18

Finding the Farthest in High Dimensions: Dynamic Diameter and Farthest-Neighbor Search

cs.DS ·2026-11-12 ·Mohammad Hajiaghayi, Morteza Monemizadeh
similarity 0.59
Abstract

We give algorithms for maintaining diameter in the dynamic model, and for answering farthest-neighbor queries on a fixed point set, in high-dimensional Euclidean space. For every fixed $1<c<\sqrt2$, update horizon $t$, and error probability $δ$, we maintain an actual factor-$c$ diameter pair with worst-case update time $n^{2/c^2-1}\text{poly}_c(d,\log(2nt/δ))$ and space $n^{2/c^2}\text{poly}_c(d,\log(2nt/δ))$. Here $n$ bounds the number of active point identities. The update exponent improves Indyk's SODA~2003 bound from $1/c^2$ to $2/c^2-1$, while the space exponent improves from $1+1/c^2$ to $2/c^2$. At $c=\sqrt{3/2}$, the update exponent decreases from $2/3$ to $1/3$. A separate construction achieves approximation exactly $\sqrt2$ with update time polynomial in $d$ and $\log(2nt/δ)$. With probability at least $1-δ$, every maintained answer during the first $t$ updates is correct, even when updates depend on all previous answers and random choices. A second construction improves the update exponent when the space exponent is close to one. On rational inputs, it has an always-correct variant with expected amortized update bounds over every fixed finite prefix of an adaptive execution, without an advance update horizon. The dynamic structures store a current answer, so reporting its two point identifiers takes constant time. The geometric method also gives static diameter algorithms and a farthest-neighbor structure for a fixed set that answers arbitrary adaptive queries. At approximation $\sqrt2-\varepsilon$, the diameter time is $n^{1+O(\varepsilon)}$, and the query time is $n^{O(\varepsilon)+o(1)}$ with near-linear preprocessing and space, up to polynomial input-parameter factors.

0.25

Two-point Approximate Shortest Path Queries among Convex Polygonal Obstacles in the Plane

cs.CG ·2026-08-10 ·Siddharth Gaur, R. Inkulu
similarity 0.59
Abstract

Given a polygonal domain $\cal P$ consisting $h$ pairwise disjoint convex polygonal obstacles together defined with $n$ vertices and a positive real number $ε$ in $(0, 0.6)$, this paper presents an algorithm to preprocess $\cal P$ in $O(n+\frac{h}ε(h+\frac{1}{\sqrtε})\lg(\frac{h}{\sqrtε}))$ time to compute data structures of size $O(n+\frac{h}{\sqrtε} (h+\frac{1}ε))$ so that given any two points $s$ and $t$ in the free space defined by $\cal P$, a path between $s$ and $t$ with a $(1+ε)$ multiplicative stretch and $13\ell$ additive stretch is output in $O(\frac{1}{\sqrtε}(\lg{\frac{h}{\sqrtε}})+\frac{h}{ε^{2.5}}(\lg{\lg(\frac{h}{\sqrtε})}))$ time. Here, $\ell$ is upper bounded by $(\sqrt{2ε}) (\max_{P_i \in \cal P} \max_{p, q \in P_i} |pq|)$.

0.04

Constant Approximation of Fréchet Distance in Near-Linear Time

cs.CG ·2026-10-30 ·Haoqiang Huang, Zihe Wang, Shuo Zhang
similarity 0.58
Abstract

We give the first constant-factor approximation for the Fréchet distance in near-linear time. Given two polygonal curves in $\mathbb{R}^d$ with $n$ and $m$ vertices, respectively, where $m\le n$, our deterministic algorithm runs in $O(n^{1+\varepsilon})$ time for every fixed $\varepsilon>0$ and $d$, with an approximation factor depending only on $\varepsilon$ and $d$. The same result holds for the discrete Fréchet distance. Our result extends the line of work initiated by Cheng, Huang, and Zhang (STOC 2025) from strongly subquadratic to near-linear time. Our algorithm recursively balances preprocessing and query time. An index for comparing subcurves of a single curve supports faster queries between different curves. We obtain this speedup by replacing one curve with surrogates assembled from indexed subcurves of the other and shared across starting points of matchings. Faster queries then reduce the cost of building the next index. Compact boundary reachability summaries allow the answers to be reused in later recursive calls. After a number of rounds depending only on $\varepsilon$, both preprocessing and query time are near-linear.

0.15