TY - GEN
T1 - Constructing pairwise disjoint paths with few links
AU - Gupta, Himanshu
AU - Wenger, Rephael
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.
PY - 1997
Y1 - 1997
N2 - Let P be a simple polygon and let {(formula presented)} be m pairs of distinct vertices of P where for every distinct i, j ≤ m, there exist pairwise disjoint paths connecting u i to (formula presented). We wish to construct m Pairwise disjoint paths in the interior of P connecting u i to (formula presented) for i = 1, ..., m, with minimal total number of line segments. We give an approximation algorithm which in O(n log m + M log m) time constructs such a set of paths using O(M) line segments where M is the number of line segments in the optimal solution.
AB - Let P be a simple polygon and let {(formula presented)} be m pairs of distinct vertices of P where for every distinct i, j ≤ m, there exist pairwise disjoint paths connecting u i to (formula presented). We wish to construct m Pairwise disjoint paths in the interior of P connecting u i to (formula presented) for i = 1, ..., m, with minimal total number of line segments. We give an approximation algorithm which in O(n log m + M log m) time constructs such a set of paths using O(M) line segments where M is the number of line segments in the optimal solution.
UR - https://www.scopus.com/pages/publications/84947907256
U2 - 10.1007/3-540-63307-3_79
DO - 10.1007/3-540-63307-3_79
M3 - Conference contribution
AN - SCOPUS:84947907256
SN - 3540633073
SN - 9783540633075
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 416
EP - 425
BT - Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings
A2 - Dehne, Frank
A2 - Sack, Jorg-Rudiger
A2 - Rau-Chaplin, Andrew
A2 - Tamassia, Roberto
PB - Springer Verlag
T2 - 5th International Workshop on Algorithms and Data Structures, WADS 1997
Y2 - 6 August 1997 through 8 August 1997
ER -