Routing in histograms

Man Kwun Chiu, Jonas Cleve, Klost Katharina, Matias Korman, Wolfgang Mulzer, A.M. van Renssen, Marcel Roeloffzen, Max Willert

Onderzoeksoutput: Bijdrage aan congresAbstract

5 Downloads (Pure)


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
Originele taal-2Engels
Aantal pagina's8
StatusGepubliceerd - 18 mrt 2019
Evenement35th European Workshop on Computational Geometry (EuroCG 2019) - Utrecht, Nederland
Duur: 18 mrt 201920 mrt 2019
Congresnummer: 35


Workshop35th European Workshop on Computational Geometry (EuroCG 2019)
Verkorte titelEuroCG
Internet adres


Citeer dit

Chiu, M. K., Cleve, J., Katharina, K., Korman, M., Mulzer, W., van Renssen, A. M., ... Willert, M. (2019). Routing in histograms. 18:1-18:8. Abstract van 35th European Workshop on Computational Geometry (EuroCG 2019), Utrecht, Nederland.