摘要: Let π(a, b) denote the shortest path between two points a, b inside a simple polygon P, which totally lies in P. The geodesic distance and bin P is defined as length of π (a, b), denoted by gd(a, contrast with Euclidean b, d(a, b). Given disjoint polygons Pand Q plane, bridge problem asks for line segment (optimal bridge)that connects point p on boundary q such that sum three distances gd(p′, p), d(p, q)and gd(q, q′), any p′ ∈ q′ Q, minimized. We present an O(nlog3n) time algorithm finding optimal polygons. This significantly improves upon previous O(n2)time bound.
springer.com
sci-hub.st 参考文章(12)
Takeshi Tokuyama, Efficient Algorithms for the Minimum Diameter Bridge Problem JCDCG '00 Revised Papers from the Japanese Conference on Discrete and Computational Geometry. pp. 362- 369 ,(2000) , 10.1007/3-540-47738-1_34
Xuehou Tan, On optimal bridges between two convex regions Information Processing Letters. ,vol. 76, pp. 163- 168 ,(2000) , 10.1016/S0020-0190(00)00143-5
Neil Sarnak, Robert E. Tarjan, Planar point location using persistent search trees Communications of The ACM. ,vol. 29, pp. 669- 679 ,(1986) , 10.1145/6138.6151
D.P. Wang, An optimal algorithm for constructing an optimal bridge between two simple rectilinear polygons Information Processing Letters. ,vol. 79, pp. 229- 236 ,(2001) , 10.1016/S0020-0190(00)00229-5
Boris Aronov, Steven Fortune, Gordon Wilfong, The furthest-site geodesic voronoi diagram Discrete and Computational Geometry. ,vol. 9, pp. 217- 255 ,(1993) , 10.1007/BF02189321
Cai Leizhen, Xu Yinfeng, Zhu Binhai, Computing the optimal bridge between two convex polygons Information Processing Letters. ,vol. 69, pp. 127- 130 ,(1999) , 10.1016/S0020-0190(99)00003-4
Leonidas J. Guibas, John Hershberger, Optimal shortest path queries in a simple polygon Journal of Computer and System Sciences. ,vol. 39, pp. 126- 152 ,(1989) , 10.1016/0022-0000(89)90041-X
Jin-Yi Cai, A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes Information Processing Letters. ,vol. 69, pp. 167- 174 ,(1999) , 10.1016/S0020-0190(99)00011-3
Michael T Goodrich, Roberto Tamassia, Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations Journal of Algorithms. ,vol. 23, pp. 51- 73 ,(1997) , 10.1006/JAGM.1995.0797
Sung Kwon Kim, Chan-Su Shin, Computing the Optimal Bridge between Two Polygons Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 34, pp. 337- 352 ,(2001) , 10.1007/S00224-001-1018-2