New and improved spanning ratios for Yao graphs
<p><span>For a set of points in the plane and a fixed integer $k > 0$, the Yao </span><span>graph $Y_k$ partitions the space around each point into $k$ </span><span>equiangular cones of angle $\theta=2\pi/k$, and connects each point to </span><span...
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Carleton University
2015-01-01
|
| Series: | Journal of Computational Geometry |
| Online Access: | http://jocg.org/index.php/jocg/article/view/190 |
| _version_ | 1819237783253811200 |
|---|---|
| author | Luis Barba Prosenjit Bose Mirela Damian Rolf Fagerberg Wah Loon Keng Joseph O'Rourke André van Renssen Perouz Taslakian Sander Verdonschot Ge Xia |
| author_facet | Luis Barba Prosenjit Bose Mirela Damian Rolf Fagerberg Wah Loon Keng Joseph O'Rourke André van Renssen Perouz Taslakian Sander Verdonschot Ge Xia |
| author_sort | Luis Barba |
| collection | DOAJ |
| description | <p><span>For a set of points in the plane and a fixed integer $k > 0$, the Yao </span><span>graph $Y_k$ partitions the space around each point into $k$ </span><span>equiangular cones of angle $\theta=2\pi/k$, and connects each point to </span><span>a nearest neighbor in each cone. It is known for all Yao graphs, with </span><span>the sole exception of $Y_5$, whether or not they are geometric </span><span>spanners. In this paper we close this gap by showing that for odd $k </span><span>\geq 5$, the spanning ratio of $Y_k$ is at most </span><span>$1/(1-2\sin(3\theta/8))$, which gives the first constant upper bound </span><span>for $Y_5$, and is an improvement over the previous bound of </span><span>$1/(1-2\sin(\theta/2))$ for odd $k \geq 7$.</span><br /><br /><span>We further reduce the upper bound on the spanning ratio for $Y_5$ from </span><span>$10.9$ to \mbox{$2+\sqrt{3} \approx 3.74$}, which falls slightly below </span><span>the lower bound of $3.79$ established for the spanning ratio of </span><span>$\Theta_5$ ($\Theta$-graphs differ from Yao graphs only in the way </span><span>they select the closest neighbor in each cone). This is the first such </span><span>separation between a Yao and $\Theta$-graph with the same number of </span><span>cones. We also give a lower bound of $2.87$ on the spanning ratio of </span><span>$Y_5$.</span><br /><br /><span>In addition, we revisit the $Y_6$ graph, which plays a particularly </span><span>important role as the transition between the graphs ($k > 6$) for </span><span>which simple inductive proofs are known, and the graphs ($k \le 6$) </span><span>whose best spanning ratios have been established by complex arguments. </span><span>Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, </span><span>getting closer to the spanning ratio of 2 established for $\Theta_6$. </span></p><p><span>Finally, we present the first lower bounds on the spanning ratio of </span><span>Yao graphs with more than six cones, and a construction that shows </span><span>that the Yao-Yao graph (a bounded-degree variant of the Yao graph) </span><span>with five cones is not a spanner.</span></p><div class="yj6qo ajU"> </div> |
| first_indexed | 2024-12-23T13:25:49Z |
| format | Article |
| id | doaj.art-5a1e46b0dea642a4bcd40d008b76bf3a |
| institution | Directory Open Access Journal |
| issn | 1920-180X |
| language | English |
| last_indexed | 2024-12-23T13:25:49Z |
| publishDate | 2015-01-01 |
| publisher | Carleton University |
| record_format | Article |
| series | Journal of Computational Geometry |
| spelling | doaj.art-5a1e46b0dea642a4bcd40d008b76bf3a2022-12-21T17:45:18ZengCarleton UniversityJournal of Computational Geometry1920-180X2015-01-016210.20382/jocg.v6i2a359New and improved spanning ratios for Yao graphsLuis Barba0Prosenjit Bose1Mirela Damian2Rolf Fagerberg3Wah Loon Keng4Joseph O'Rourke5André van Renssen6Perouz Taslakian7Sander Verdonschot8Ge Xia9School of Computer Science, Carleton University; Département d’Informatique, Université Libre de BruxellesSchool of Computer Science, Carleton UniversityDepartment of Computing Sciences, Villanova UniversityDepartment of Computer Science, University of Southern DenmarkDepartment of Computer Science, Lafayette CollegeDepartment of Computer Science, Smith CollegeJST, ERATO, Kawarabayashi Large Graph Project, National Institute of Informatics (NII)School of Science and Engineering, American University of ArmeniaSchool of Computer Science, Carleton UniversityDepartment of Computer Science, Lafayette College<p><span>For a set of points in the plane and a fixed integer $k > 0$, the Yao </span><span>graph $Y_k$ partitions the space around each point into $k$ </span><span>equiangular cones of angle $\theta=2\pi/k$, and connects each point to </span><span>a nearest neighbor in each cone. It is known for all Yao graphs, with </span><span>the sole exception of $Y_5$, whether or not they are geometric </span><span>spanners. In this paper we close this gap by showing that for odd $k </span><span>\geq 5$, the spanning ratio of $Y_k$ is at most </span><span>$1/(1-2\sin(3\theta/8))$, which gives the first constant upper bound </span><span>for $Y_5$, and is an improvement over the previous bound of </span><span>$1/(1-2\sin(\theta/2))$ for odd $k \geq 7$.</span><br /><br /><span>We further reduce the upper bound on the spanning ratio for $Y_5$ from </span><span>$10.9$ to \mbox{$2+\sqrt{3} \approx 3.74$}, which falls slightly below </span><span>the lower bound of $3.79$ established for the spanning ratio of </span><span>$\Theta_5$ ($\Theta$-graphs differ from Yao graphs only in the way </span><span>they select the closest neighbor in each cone). This is the first such </span><span>separation between a Yao and $\Theta$-graph with the same number of </span><span>cones. We also give a lower bound of $2.87$ on the spanning ratio of </span><span>$Y_5$.</span><br /><br /><span>In addition, we revisit the $Y_6$ graph, which plays a particularly </span><span>important role as the transition between the graphs ($k > 6$) for </span><span>which simple inductive proofs are known, and the graphs ($k \le 6$) </span><span>whose best spanning ratios have been established by complex arguments. </span><span>Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, </span><span>getting closer to the spanning ratio of 2 established for $\Theta_6$. </span></p><p><span>Finally, we present the first lower bounds on the spanning ratio of </span><span>Yao graphs with more than six cones, and a construction that shows </span><span>that the Yao-Yao graph (a bounded-degree variant of the Yao graph) </span><span>with five cones is not a spanner.</span></p><div class="yj6qo ajU"> </div>http://jocg.org/index.php/jocg/article/view/190 |
| spellingShingle | Luis Barba Prosenjit Bose Mirela Damian Rolf Fagerberg Wah Loon Keng Joseph O'Rourke André van Renssen Perouz Taslakian Sander Verdonschot Ge Xia New and improved spanning ratios for Yao graphs Journal of Computational Geometry |
| title | New and improved spanning ratios for Yao graphs |
| title_full | New and improved spanning ratios for Yao graphs |
| title_fullStr | New and improved spanning ratios for Yao graphs |
| title_full_unstemmed | New and improved spanning ratios for Yao graphs |
| title_short | New and improved spanning ratios for Yao graphs |
| title_sort | new and improved spanning ratios for yao graphs |
| url | http://jocg.org/index.php/jocg/article/view/190 |
| work_keys_str_mv | AT luisbarba newandimprovedspanningratiosforyaographs AT prosenjitbose newandimprovedspanningratiosforyaographs AT mireladamian newandimprovedspanningratiosforyaographs AT rolffagerberg newandimprovedspanningratiosforyaographs AT wahloonkeng newandimprovedspanningratiosforyaographs AT josephorourke newandimprovedspanningratiosforyaographs AT andrevanrenssen newandimprovedspanningratiosforyaographs AT perouztaslakian newandimprovedspanningratiosforyaographs AT sanderverdonschot newandimprovedspanningratiosforyaographs AT gexia newandimprovedspanningratiosforyaographs |