Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2306.17097 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908645639323648 |
|---|---|
| author | Buchin, Kevin Gudmundsson, Joachim Kalb, Antonia Popov, Aleksandr Rehs, Carolin van Renssen, André Wong, Sampson |
| author_facet | Buchin, Kevin Gudmundsson, Joachim Kalb, Antonia Popov, Aleksandr Rehs, Carolin van Renssen, André Wong, Sampson |
| contents | Given a point set $P$ in the Euclidean plane and a parameter $t$, we define an \emph{oriented $t$-spanner} $G$ as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest closed walk in $G$ through those points is at most a factor $t$ longer than the shortest cycle in the complete graph on $P$. We investigate the problem of computing sparse graphs with small oriented dilation.
As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a $1$-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face.
This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in $\mathcal{O}(n^7)$ time for $n$ points, and a greedy algorithm that computes a $5$-spanner in $\mathcal{O}(n\log n)$ time.
Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in a plane oriented $t$-spanner with $t=7.2 \cdot t_g$, where $t_g$ is an upper bound on the dilation of the greedy triangulation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_17097 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Oriented Spanners Buchin, Kevin Gudmundsson, Joachim Kalb, Antonia Popov, Aleksandr Rehs, Carolin van Renssen, André Wong, Sampson Computational Geometry Given a point set $P$ in the Euclidean plane and a parameter $t$, we define an \emph{oriented $t$-spanner} $G$ as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest closed walk in $G$ through those points is at most a factor $t$ longer than the shortest cycle in the complete graph on $P$. We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a $1$-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in $\mathcal{O}(n^7)$ time for $n$ points, and a greedy algorithm that computes a $5$-spanner in $\mathcal{O}(n\log n)$ time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in a plane oriented $t$-spanner with $t=7.2 \cdot t_g$, where $t_g$ is an upper bound on the dilation of the greedy triangulation. |
| title | Oriented Spanners |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2306.17097 |