TY - JOUR A1 - Banyassady, Bahareh A1 - Chiu, Man-Kwun A1 - Korman, Matias A1 - Mulzer, Wolfgang A1 - van Renssen, André A1 - Roeloffzen, Marcel A1 - Seiferth, Paul A1 - Stein, Yannik A1 - Vogtenhuber, Birgit A1 - Willert, Max T1 - Routing in polygonal domains JF - Computational Geometry, Theory and Applications N2 - We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. 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 data packet between any two vertices p and q of P, where each step must use only the label of the target node q and the routing table of the current node. For any fixed epsilon > 0, we present a routing scheme that always achieves a routing path whose length exceeds the shortest path by a factor of at most 1 + epsilon. The labels have O(log n) bits, and the routing tables are of size O(((epsilon^-1)+h)log n). The preprocessing time is O((n^2)log n). It can be improved to O(n^2) for simple polygons. Y1 - 2019 U6 - https://doi.org/10.1016/j.comgeo.2019.101593 VL - 87 PB - Elsevier ER - TY - JOUR A1 - Banyassady, Bahareh A1 - Barba, Luis A1 - Mulzer, Wolfgang T1 - Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees JF - Journal of Computational Geometry (JoCG) N2 - We present time-space trade-offs for computing the Euclidean minimum spanning tree of a set S of n point-sites in the plane. More precisely, we assume that S resides in a random-access memory that can only be read. The edges of the Euclidean minimum spanning tree EMST(S) have to be reported sequentially, and they cannot be accessed or modified afterwards. There is a parameter s in {1, ..., n} so that the algorithm may use O(s) cells of read-write memory (called the workspace) for its computations. Our goal is to find an algorithm that has the best possible running time for any given s between 1 and n. We show how to compute EMST(S) in O(((n^3)/(s^2)) log s) time with O(s) cells of workspace, giving a smooth trade-off between the two best-known bounds O(n^3) for s = 1 and O(n log n) for s = n. For this, we run Kruskal's algorithm on the "relative neighborhood graph" (RNG) of S. It is a classic fact that the minimum spanning tree of RNG(S) is exactly EMST(S). To implement Kruskal's algorithm with O(s) cells of workspace, we define s-nets, a compact representation of planar graphs. This allows us to efficiently maintain and update the components of the current minimum spanning forest as the edges are being inserted. Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?https://jocg.org/index.php/jocg/article/view/473 VL - 11(1) SP - 525 EP - 547 ER -