Name
Abstract | ||
|---|---|---|
Let P be a simple polygon and let {(u1, u′1), (u2, u′2),…,(um, u′m)} be a set of m pairs of distinct vertices of P, where for every distinct i, j ≤ m, there exist pairwise disjoint (nonintersecting) paths connecting ui to u′i and uj to u′j. We wish to construct m pairwise disjoint paths in the interior of P connecting ui to u′i for i = 1, …,m, with a minimal total number of line segments. We give an approximation algorithm that constructs such a set of paths using O(M) line segments in O(n log m + M log m) time, where M is the number of line segments in the optimal solution and n is the size of the polygon. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1273340.1273342 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
noncrossing,distinct vertex,m log m,m pairwise disjoint path,pairwise disjoint,minimal total number,distinct i,simple polygon,polygon,isomorphic triangulations,n log m,line segment,m pair,link paths | Approximation algorithm,Discrete mathematics,Line segment,Combinatorics,Disjoint sets,Vertex (geometry),Computational geometry,Triangulation (social science),Simple polygon,Mathematics | Journal |
Volume | Issue | ISSN |
3 | 3 | 1549-6325 |
ISBN | Citations | PageRank |
3-540-63307-3 | 6 | 0.64 |
References | Authors | |
26 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Himanshu Gupta | 1 | 2653 | 277.86 |
| Rephael Wenger | 2 | 441 | 43.54 |