## Abstract

Let P be a histogram with n vertices, i.e., an x-monotone orthogonal polygon whose upper boundary is a single edge. Two points p, q ∈ P are co-visible if and only if the (axis-parallel) bounding rectangle of p and q is in P. In the r-visibility graph of P, we connect two vertices of P with an unweighted edge if and only if they are co-visible. We consider routing with preprocessing in P. We may preprocess P to obtain a label and a routing table for each vertex of P. Then, we

must be able to route a packet between any two vertices s and t of P, where each step may use only the label of the target node t, the routing table, and the neighborhood of the current node. We present a routing scheme for histograms that sends any data packet along a shortest path. Each label needs O(log n) bits, while the routing table of each node consists of a single bit

must be able to route a packet between any two vertices s and t of P, where each step may use only the label of the target node t, the routing table, and the neighborhood of the current node. We present a routing scheme for histograms that sends any data packet along a shortest path. Each label needs O(log n) bits, while the routing table of each node consists of a single bit

Original language | English |
---|---|

Pages | 18:1-18:8 |

Number of pages | 8 |

Publication status | Published - 18 Mar 2019 |

Event | 35th European Workshop on Computational Geometry (EuroCG 2019) - Utrecht, Netherlands Duration: 18 Mar 2019 → 20 Mar 2019 Conference number: 35 http://www.eurocg2019.uu.nl/ |

### Workshop

Workshop | 35th European Workshop on Computational Geometry (EuroCG 2019) |
---|---|

Abbreviated title | EuroCG |

Country/Territory | Netherlands |

City | Utrecht |

Period | 18/03/19 → 20/03/19 |

Internet address |