Back to Search
Start Over
Finding an Optimal Bridge Between Two Polygons.
- Source :
-
International Journal of Computational Geometry & Applications . Jun2002, Vol. 12 Issue 3, p249. 13p. - Publication Year :
- 2002
-
Abstract
- 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 between a and b in P is defined as the length of π(a, b), denoted by gd(a, b), in contrast with the Euclidean distance between a and b in the plane, denoted by d(a, b). Given two disjoint polygons P and Q in the plane, the bridge problem asks for a line segment (optimal bridge) that connects a point p on the boundary of P and a point q on the boundary of Q such that the sum of three distances gd(p', p), d(p, q) and gd(q, q'), with any p' ∈ P and any q' ∈ Q, is minimized. We present an O(n log³ n) time algorithm for finding an optimal bridge between two simple polygons. This significantly improves upon the previous O(n²) time bound. Our result is obtained by making substantial use of a hierarchical structure that consists of segment trees, range trees and persistent search trees, and a structure that supports dynamic ray shooting and shortest path queries as well. [ABSTRACT FROM AUTHOR]
- Subjects :
- *DATA structures
*MATHEMATICAL optimization
*VORONOI polygons
*G-spaces
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 12
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 7227413
- Full Text :
- https://doi.org/10.1142/S0218195902000852