Spanners of Additively Weighted Point Sets

Details Spanners of Additively Weighted Point Sets Spanners of Additively Weighted Point Sets

2008-01-25

arxiv.org/abs/0801.4013v1

Computer Science

Computational Geometry

Scientific paper

We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs $(p,r)$ where $p$ is a point in the plane and $r$ is a real number. The distance between two points $(p_i,r_i)$ and $(p_j,r_j)$ is defined as $|p_ip_j|-r_i-r_j$. We show that in the case where all $r_i$ are positive numbers and $|p_ip_j|\geq r_i+r_j$ for all $i,j$ (in which case the points can be seen as non-intersecting disks in the plane), a variant of the Yao graph is a $(1+\epsilon)$-spanner that has a linear number of edges. We also show that the Additively Weighted Delaunay graph (the face-dual of the Additively Weighted Voronoi diagram) has constant spanning ratio. The straight line embedding of the Additively Weighted Delaunay graph may not be a plane graph. We show how to compute a plane embedding that also has a constant spanning ratio.

Affiliated with

Also associated with

No associations

Rating

Spanners of Additively Weighted Point Sets 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 Spanners of Additively Weighted Point Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanners of Additively Weighted Point Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-413273