Zobrazeno 1 - 10
of 56
pro vyhledávání: '"Steiner spanners"'
Autor:
Bhore, Sujoy, Keszegh, Balázs, Kupavskii, Andrey, Le, Hung, Louvet, Alexandre, Pálvölgyi, Dömötör, Tóth, Csaba D.
We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant $\epsilon\in (0,1)$, one could construct a $(2+\epsilon)$-spanner with $O(n\log(n))$ edges (SICOMP 20
Externí odkaz:
http://arxiv.org/abs/2404.05045
Autor:
Bhore, Sujoy, Toth, Csaba D.
Lightness and sparsity are two natural parameters for Euclidean $(1+\varepsilon)$-spanners. Classical results show that, when the dimension $d\in \mathbb{N}$ and $\varepsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits an $(1+\va
Externí odkaz:
http://arxiv.org/abs/2206.09648
Autor:
Bhore, Sujoy, Tóth, Csaba D.
Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in $\mathbb{R}^d$. In a recent breakthrough, Le and Solomon (2019) established the
Externí odkaz:
http://arxiv.org/abs/2012.02216
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Borradaile, Glencora, Eppstein, David
Publikováno v:
Comp. Geom. Theory & Applications 49: 8-16, 2015
We describe an algorithm that takes as input n points in the plane and a parameter {\epsilon}, and produces as output an embedded planar graph having the given points as a subset of its vertices in which the graph distances are a (1 + {\epsilon})-app
Externí odkaz:
http://arxiv.org/abs/1206.2254
Autor:
Borradaile, Glencora, Eppstein, David
Publikováno v:
In Computational Geometry: Theory and Applications November 2015 49:8-16
Autor:
Sujoy Bhore, Csaba D. Tóth
Publikováno v:
SIAM Journal on Discrete Mathematics. 36:2411-2444
Lightness and sparsity are two natural parameters for Euclidean $(1+\varepsilon)$-spanners. Classical results show that, when the dimension $d\in \mathbb{N}$ and $\varepsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits an $(1+\va
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d81b20c5d90b72aa194ec71486761639
https://doi.org/10.1137/22m1502707
https://doi.org/10.1137/22m1502707
Conference
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
David Eppstein, Glencora Borradaile
Publikováno v:
Computational Geometry. 49:8-16
We describe an algorithm that takes as input n points in the plane and a parameter ϵ, and produces as output an embedded planar graph having the given points as a subset of its vertices in which the graph distances are a ( 1 + ϵ ) -approximation to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e870d1e5689ab5e704b588a0832d1afe
https://doi.org/10.1016/j.comgeo.2015.04.005
https://doi.org/10.1016/j.comgeo.2015.04.005
Conference
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.