Bounded Degree Planar Geometric Spanners - Computer Science > Computational GeometryReportar como inadecuado




Bounded Degree Planar Geometric Spanners - Computer Science > Computational Geometry - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Given a set $P$ of $n$ points in the plane, we show how to compute in $On\log n$ time a subgraph of their Delaunay triangulation that has maximumdegree 7 and is a strong planar $t$-spanner of $P$ with $t =1+ \sqrt{2}^2*\delta$, where $\delta$ is the spanning ratio of the Delaunay triangulation.Furthermore, given a Delaunay triangulation, we show a distributed algorithmthat computes the same bounded degree planar spanner in On time.



Autor: Paz Carmi, Lilach Chaitman

Fuente: https://arxiv.org/







Documentos relacionados