Spanners of Additively Weighted Point Sets
| dc.creator | Bose, Prosenjit | |
| dc.creator | Carmi, Paz | |
| dc.creator | Couture, Mathieu | |
| dc.date | 2008-01-25 | |
| dc.date.accessioned | 2026-07-07T08:56:33Z | |
| dc.date.available | 2026-07-07T08:56:33Z | |
| dc.description | 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+ε)$-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. | |
| dc.identifier | https://arxiv.org/abs/0801.4013 | |
| dc.identifier | http://arxiv.org/abs/0801.4013 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/146650 | |
| dc.subject | Computational Geometry | |
| dc.title | Spanners of Additively Weighted Point Sets | |
| dc.type | text |