Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.02856 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911190695804928 |
|---|---|
| author | Chandran, Sreehari Inkulu, R. |
| author_facet | Chandran, Sreehari Inkulu, R. |
| contents | Given a convex polytope $P$ defined with $n$ vertices in $\mathbb{R}^3$, this paper presents an algorithm to preprocess $P$ to compute routing tables at every vertex of $P$ so that a data packet can be routed on $P$ from any vertex of $P$ to any other vertex of $P$. At every vertex $v$ of $P$ along the routing path, until the packet reaches its destination, the next hop is determined using the routing tables at $v$ and the information stored in the packet header. In $O(n+\min(n^3, \frac{1}{ε^7}))$ time, the preprocessing algorithm computes a routing table at every vertex of $P$ of amortized size $O(\min(n, \frac{1}{ε^{3/2}}))$ bits. If the optimal shortest distance between $s$ and $t$ on $P$ is $d(s, t)$, then the routing path produced by this algorithm has length at most $\frac{8+ε}{\sin{θ_m}}(D+d(s,t))$. Here, $ε\in (0, 1)$ is an input parameter, $D$ is the maximum length of the diagonal of any cell when $\partial P$ is partitioned into $\frac{1}{ε^3}$ geodesic cells of equal size, and $θ_m$ is half the minimum angle between any two neighbouring edges of $P$ on $\partial P$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02856 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local Routing on a Convex Polytope in R^3 Chandran, Sreehari Inkulu, R. Computational Geometry Given a convex polytope $P$ defined with $n$ vertices in $\mathbb{R}^3$, this paper presents an algorithm to preprocess $P$ to compute routing tables at every vertex of $P$ so that a data packet can be routed on $P$ from any vertex of $P$ to any other vertex of $P$. At every vertex $v$ of $P$ along the routing path, until the packet reaches its destination, the next hop is determined using the routing tables at $v$ and the information stored in the packet header. In $O(n+\min(n^3, \frac{1}{ε^7}))$ time, the preprocessing algorithm computes a routing table at every vertex of $P$ of amortized size $O(\min(n, \frac{1}{ε^{3/2}}))$ bits. If the optimal shortest distance between $s$ and $t$ on $P$ is $d(s, t)$, then the routing path produced by this algorithm has length at most $\frac{8+ε}{\sin{θ_m}}(D+d(s,t))$. Here, $ε\in (0, 1)$ is an input parameter, $D$ is the maximum length of the diagonal of any cell when $\partial P$ is partitioned into $\frac{1}{ε^3}$ geodesic cells of equal size, and $θ_m$ is half the minimum angle between any two neighbouring edges of $P$ on $\partial P$. |
| title | Local Routing on a Convex Polytope in R^3 |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2510.02856 |