Med tanke på en triangulation G, vars vertex uppsättning V är en uppsättning n punkter i planet, och med tanke på ett reellt antal γ med 0 < γ < π, designar vi en O (n)-tids algoritm som konstruerar en ansluten subgraf G av G med vertex set V vars maximala grad är högst 14 + 2π/γ. Om G är Delaunay triangulation av V, och γ = 2π/3, visar vi att G är en t-spanner av V (för vissa konstant t) med maximal grad på högst 17, vilket förbättrar den tidigare mest kända graden bundet av 23. Om G är en triangulation som uppfyller diamanten egenskap, då för ett specifikt intervall av värden av γ beroende på vinkeln på diamanterna, visar vi att G är en t-spanner av V (för vissa konstant t) vars högsta grad begränsas av en konstant beroende på γ. Om G är grafen som består av alla Delaunay kanter av längd högst 1, och γ = π/3, visar vi att en modifierad version av algoritmen producerar en plan subgraph G av enhet-disk grafen som är en t-spanner (för vissa konstant t) av den enhet-disk grafen av V, vars maximala grad är högst 20, vilket förbättrar den tidigare mest kända graden bundet av 25.
I REF presenteras en O(n)-tidsalgoritm som konstruerar en ansluten subgraf av en given triangulation vars maximala grad är högst 14 +  för ett givet reellt tal γ, där 0 < γ < π.
Delaunay and Diamond Triangulations Contain Spanners of Bounded Degree
{'venue': 'Int. J. Comput. Geometry Appl.', 'journal': 'Int. J. Comput. Geometry Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}