Bounded Degree Planar Geometric Spanners

Details Bounded Degree Planar Geometric Spanners Bounded Degree Planar Geometric Spanners

2010-03-25

arxiv.org/abs/1003.4963v1

Computer Science

Computational Geometry

Scientific paper

Given a set $P$ of $n$ points in the plane, we show how to compute in $O(n \log n)$ time a subgraph of their Delaunay triangulation that has maximum degree 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 algorithm that computes the same bounded degree planar spanner in O(n) time.

Affiliated with

Also associated with

No associations

Rating

Bounded Degree Planar Geometric Spanners does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounded Degree Planar Geometric Spanners, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounded Degree Planar Geometric Spanners will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-556856