×

Routing in polygonal domains. (English) Zbl 1433.68276

Summary: 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 \(\varepsilon > 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 + \varepsilon\). The labels have \(O(\log n)\) bits, and the routing tables are of size \(O(( \varepsilon^{- 1} + h) \log n)\). The preprocessing time is \(O( n^2 \log n)\). It can be improved to \(O( n^2)\) for simple polygons.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abraham, I.; Gavoille, C., On approximate distance labels and routing schemes with affine stretch, (Proc. 25th Int. Symp. Dist. Comp. (DISC) (2011)), 404-415 · Zbl 1350.68020
[2] Asano, T.; Asano, T.; Guibas, L.; Hershberger, J.; Imai, H., Visibility of disjoint polygons, Algorithmica, 1, 1-4, 49-63 (1986) · Zbl 0611.68062
[3] Awerbuch, B.; Bar-Noy, A.; Linial, N.; Peleg, D., Improved routing strategies with succinct tables, J. Algorithms, 11, 3, 307-341 (1990) · Zbl 0724.68004
[4] Bar-Yehuda, R.; Chazelle, B., Triangulating disjoint Jordan chains, Int. J. Comput. Geom. Appl., 4, 04, 475-481 (1994) · Zbl 0829.68124
[5] Barba, L.; Bose, P.; Damian, M.; Fagerberg, R.; Keng, W. L.; O’Rourke, J.; van Renssen, A.; Taslakian, P.; Verdonschot, S.; Xia, G., New and improved spanning ratios for Yao graphs, J. Comput. Geom., 6, 2, 19-53 (2015) · Zbl 1395.68282
[6] Barba, L.; Bose, P.; De Carufel, J.-L.; van Renssen, A.; Verdonschot, S., On the stretch factor of the theta-4 graph, (Proc. 13th Int. Sympos. Algorithms and Data Structures (WADS) (2013)), 109-120 · Zbl 1269.68105
[7] Bose, P.; Carufel, J.-L. D.; Morin, P.; van Renssen, A.; Verdonschot, S., Towards tight bounds on theta-graphs: more is not always better, Theor. Comput. Sci., 616, 70-93 (2016) · Zbl 1334.68237
[8] Bose, P.; Damian, M.; Douïeb, K.; O’Rourke, J.; Seamone, B.; Smid, M.; Wuhrer, S., \( \pi / 2\)-angle Yao graphs are spanners, Int. J. Comput. Geom. Appl., 22, 1, 61-82 (2012) · Zbl 1251.05036
[9] Bose, P.; Fagerberg, R.; van Renssen, A.; Verdonschot, S., Optimal local routing on Delaunay triangulations defined by empty equilateral triangles, SIAM J. Comput., 44, 6, 1626-1649 (2015) · Zbl 1333.68205
[10] Bose, P.; Fagerberg, R.; van Renssen, A.; Verdonschot, S., Competitive local routing with constraints, J. Comput. Geom., 8, 1, 125-152 (2017) · Zbl 1476.68275
[11] Bose, P.; Korman, M.; van Renssen, A.; Verdonschot, S., Constrained routing between non-visible vertices, (Proc. 23rd Annu. Int. Computing and Combinatorics Conf. (2017)), 62-74 · Zbl 1434.68348
[12] Bose, P.; Korman, M.; van Renssen, A.; Verdonschot, S., Routing on the visibility graph, (Proc. 28th Annu. Internat. Sympos. Algorithms Comput. (ISAAC) (2017)), 18:1-18:12 · Zbl 1457.68280
[13] Bose, P.; Morin, P., Competitive online routing in geometric graphs, Theor. Comput. Sci., 324, 2, 273-288 (2004) · Zbl 1073.68059
[14] Bose, P.; Morin, P.; van Renssen, A.; Verdonschot, S., The \(\theta_5\)-graph is a spanner, Comput. Geom. Theory Appl., 48, 2, 108-119 (2015) · Zbl 1307.05093
[15] Bose, P.; Smid, M., On plane geometric spanners: a survey and open problems, Comput. Geom. Theory Appl., 46, 7, 818-830 (2013) · Zbl 1270.05032
[16] Chechik, S., Compact routing schemes with improved stretch, (Proc. ACM Symp. Princ. Dist. Comp. (PODC) (2013)), 33-41 · Zbl 1323.68029
[17] Clarkson, K. L., Approximation algorithms for shortest path motion planning, (Proc. 19th Annu. ACM Sympos. Theory Comput. (STOC) (1987)), 56-65
[18] Cowen, L. J., Compact routing with minimum stretch, J. Algorithms, 38, 1, 170-183 (2001) · Zbl 0969.68180
[19] Damian, M.; Nelavalli, N., Improved bounds on the stretch factor of \(y_4\), Comput. Geom. Theory Appl., 62, 14-24 (2017) · Zbl 1365.05059
[20] Damian, M.; Raudonis, K., Yao graphs span Theta graphs, Discrete Math. Algorithms Appl., 4, 02, Article 1250024 pp. (2012) · Zbl 1251.05166
[21] Eilam, T.; Gavoille, C.; Peleg, D., Compact routing schemes with low stretch factor, J. Algorithms, 46, 2, 97-114 (2003) · Zbl 1030.68106
[22] Fraigniaud, P.; Gavoille, C., Routing in trees, (Proc. 28th Internat. Colloq. Automata Lang. Program. (ICALP) (2001)), 757-772 · Zbl 0987.68001
[23] Giordano, S.; Stojmenovic, I., Position based routing algorithms for ad hoc networks: a taxonomy, (Ad Hoc Wireless Networking (2004), Springer-Verlag), 103-136
[24] Guibas, L. J.; Hershberger, J.; Leven, D.; Sharir, M.; Tarjan, R. E., Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Algorithmica, 2, 209-233 (1987) · Zbl 0642.68081
[25] Hershberger, J.; Suri, S., An optimal algorithm for Euclidean shortest paths in the plane, SIAM J. Comput., 28, 6, 2215-2256 (1999) · Zbl 0939.68157
[26] Kaplan, H.; Mulzer, W.; Roditty, L.; Seiferth, P., Routing in unit disk graphs, Algorithmica, 80, 3, 830-848 (2018) · Zbl 1390.68503
[27] Kapoor, S.; Maheshwari, S., Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles, (Proc. 4th Annu. Sympos. Comput. Geom. (SoCG) (1988)), 172-182
[28] Kapoor, S.; Maheshwari, S.; Mitchell, J. S., An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane, Discrete Comput. Geom., 18, 4, 377-383 (1997) · Zbl 0892.68047
[29] Konjevod, G.; Richa, A. W.; Xia, D., Scale-free compact routing schemes in networks of low doubling dimension, ACM Trans. Algorithms, 12, 3, Article 27 pp. (2016) · Zbl 1445.68028
[30] Mitchell, J. S., A new algorithm for shortest paths among obstacles in the plane, Ann. Math. Artif. Intell., 3, 1, 83-105 (1991) · Zbl 0875.68765
[31] Mitchell, J. S., Shortest paths among obstacles in the plane, Int. J. Comput. Geom. Appl., 6, 03, 309-332 (1996) · Zbl 0860.68109
[32] Narasimhan, G.; Smid, M., Geometric Spanner Networks (2007), Cambridge University Press · Zbl 1140.68068
[33] Overmars, M. H.; Welzl, E., New methods for computing visibility graphs, (Proc. 4th Annu. Sympos. Comput. Geom. (SoCG) (1988)), 164-171
[34] Peleg, D.; Upfal, E., A trade-off between space and efficiency for routing tables, J. ACM, 36, 3, 510-530 (1989) · Zbl 0900.68262
[35] Roditty, L.; Tov, R., New routing techniques and their applications, (Proc. ACM Symp. Princ. Dist. Comp. (PODC) (2015)), 23-32 · Zbl 1333.05298
[36] Roditty, L.; Tov, R., Close to linear space routing schemes, Distrib. Comput., 29, 1, 65-74 (2016) · Zbl 1352.68197
[37] Santoro, N.; Khatib, R., Labelling and implicit routing in networks, Comput. J., 28, 1, 5-8 (1985) · Zbl 0555.94026
[38] Sharir, M.; Schorr, A., On shortest paths in polyhedral spaces, SIAM J. Comput., 15, 1, 193-215 (1986) · Zbl 0612.68090
[39] Storer, J. A.; Reif, J. H., Shortest paths in the plane with polygonal obstacles, J. ACM, 41, 5, 982-1012 (1994) · Zbl 0814.68129
[40] Thorup, M., Compact oracles for reachability and approximate distances in planar digraphs, J. ACM, 51, 6, 993-1024 (2004) · Zbl 1125.68394
[41] Thorup, M.; Zwick, U., Compact routing schemes, (Proc. 13th ACM Symp. Par. Algo. Arch. (SPAA) (2001)), 1-10
[42] Thorup, M.; Zwick, U., Approximate distance oracles, J. ACM, 52, 1, 1-24 (2005) · Zbl 1175.68303
[43] Welzl, E., Constructing the visibility graph for n-line segments in \(\mathcal{O}( n^2)\) time, Inf. Process. Lett., 20, 4, 167-171 (1985) · Zbl 0573.68036
[44] Yan, C.; Xiang, Y.; Dragan, F. F., Compact and low delay routing labeling scheme for unit disk graphs, Comput. Geom. Theory Appl., 45, 7, 305-325 (2012) · Zbl 1252.68216
[45] Yao, A. C.-C., On constructing minimum spanning trees in k-dimensional spaces and related problems, SIAM J. Comput., 11, 4, 721-736 (1982) · Zbl 0492.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.