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)

Samenvatting

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
Pagina's18:1-18:8
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
http://www.eurocg2019.uu.nl/

Workshop

Workshop35th European Workshop on Computational Geometry (EuroCG 2019)
Verkorte titelEuroCG
LandNederland
StadUtrecht
Periode18/03/1920/03/19
Internet adres

    Vingerafdruk

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.