Geometric Spanners With Small Chromatic Number
| dc.creator | Bose, Prosenjit | |
| dc.creator | Carmi, Paz | |
| dc.creator | Couture, Mathieu | |
| dc.creator | Maheshwari, Anil | |
| dc.creator | Smid, Michiel | |
| dc.creator | Zeh, Norbert | |
| dc.date | 2007-11-01 | |
| dc.date.accessioned | 2026-07-07T08:39:53Z | |
| dc.date.available | 2026-07-07T08:39:53Z | |
| dc.description | Given an integer $k \geq 2$, we consider the problem of computing the smallest real number $t(k)$ such that for each set $P$ of points in the plane, there exists a $t(k)$-spanner for $P$ that has chromatic number at most $k$. We prove that $t(2) = 3$, $t(3) = 2$, $t(4) = \sqrt{2}$, and give upper and lower bounds on $t(k)$ for $k>4$. We also show that for any $ε>0$, there exists a $(1+ε)t(k)$-spanner for $P$ that has $O(|P|)$ edges and chromatic number at most $k$. Finally, we consider an on-line variant of the problem where the points of $P$ are given one after another, and the color of a point must be assigned at the moment the point is given. In this setting, we prove that $t(2) = 3$, $t(3) = 1+ \sqrt{3}$, $t(4) = 1+ \sqrt{2}$, and give upper and lower bounds on $t(k)$ for $k>4$. | |
| dc.identifier | https://arxiv.org/abs/0711.0114 | |
| dc.identifier | http://arxiv.org/abs/0711.0114 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/141229 | |
| dc.subject | Computational Geometry | |
| dc.title | Geometric Spanners With Small Chromatic Number | |
| dc.type | text |