Near-linear-time deterministic plane Steiner spanners for well-spaced point sets
From MaRDI portal
Publication:906836
DOI10.1016/j.comgeo.2015.04.005zbMath1329.05077arXiv1206.2254OpenAlexW3105802762MaRDI QIDQ906836
David Eppstein, Glencora Borradaile
Publication date: 29 January 2016
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1206.2254
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- On sparse spanners of weighted graphs
- Provably good mesh generation
- The isoperimetric problem for pinwheel tilings
- An O ( n log n ) approximation scheme for Steiner tree in planar graphs
- A subset spanner for Planar graphs, with application to subset TSP
- Delaunay triangulations in O (sort( n )) time and more
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Geometric Spanner Networks
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- An optimal algorithm for intersecting line segments in the plane
- Planar spanners and approximate shortest path queries among obstacles in the plane
- PARALLEL CONSTRUCTION OF QUADTREES AND QUALITY TRIANGULATIONS
