Name
Abstract | ||
|---|---|---|
We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms that are guaranteed to find a path of at most linear size between any pair of vertices of the \emph{visibility graph} of $P$ with respect to a set of constraints $S$ (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of additional information). Contrary to {\em all} existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph. Additionally, we provide lower bounds on the routing ratio of any deterministic local routing algorithm on the visibility graph. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.20382/jocg.v9i1a15 | JoCG |
DocType | Volume | Issue |
Journal | 9 | 1 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prosenjit K. Bose | 1 | 2336 | 293.75 |
| Matias Korman | 2 | 178 | 37.28 |
| Sander Verdonschot | 3 | 110 | 17.98 |
| André van Renssen | 4 | 104 | 19.30 |