The Euclidean Bottleneck Steiner Path Problem and Other Applications of (α,β)-Pair Decomposition
Tóm tắt
We consider a geometric optimization problem that arises in network design. Given a set P of n points in the plane, source and destination points s, t∈P, and an integer k>0, one has to locate k Steiner points, such that the length of the longest edge of a bottleneck path between s and t is minimized. In this paper, we present an O(nlog2
n)-time algorithm that computes an optimal solution, for any constant k. This problem was previously studied by Hou et al. (in Wireless Networks 16, 1033–1043, 2010), who gave an O(n
2logn)-time algorithm. We also study the dual version of the problem, where a value λ>0 is given (instead of k), and the goal is to locate as few Steiner points as possible, so that the length of the longest edge of a bottleneck path between s and t is at most λ. Our algorithms are based on two new geometric structures that we develop—an (α,β)-pair decomposition of P and a floor (1+ε)-spanner of P. For real numbers β>α>0, an (α,β)-pair decomposition of P is a collection
$\mathcal{W}=\{(A_{1},B_{1}),\ldots,(A_{m},B_{m})\}$
of pairs of subsets of P, satisfying the following: (i) For each pair
$(A_{i},B_{i}) \in\mathcal {W}$
, both minimum enclosing circles of A
i
and B
i
have a radius at most α, and (ii) for any p, q∈P, such that |pq|≤β, there exists a single pair
$(A_{i},B_{i}) \in\mathcal{W}$
, such that p∈A
i
and q∈B
i
, or vice versa. We construct (a compact representation of) an (α,β)-pair decomposition of P in time O((β/α)3
nlogn). In some applications, a simpler (though weaker) grid-based version of an (α,β)-pair decomposition of P is sufficient. We call this version a weak (α,β)-pair decomposition of P. For ε>0, a floor (1+ε)-spanner of P is a (1+ε)-spanner of the complete graph over P with weight function w(p,q)=⌊|pq|⌋. We construct such a spanner with O(n/ε
2) edges in time O((1/ε
2)nlog2
n), even though w is not a metric. Finally, we present two additional applications of an (α,β)-pair decomposition of P. In the first, we construct a strong spanner of the unit disk graph of P, with the additional property that the spanning paths also approximate the number of substantial hops, i.e., hops of length greater than a given threshold. In the second application, we present an O((1/ε
2)nlogn)-time algorithm for computing a one-sided approximation for distance selection (i.e., given k,
$1 \le k \le{n \choose2}$
, find the k’th smallest Euclidean distance induced by P), significantly improving the running time of the algorithm of Bespamyatnikh and Segal.
Tài liệu tham khảo
Abam, M.A., Har-Peled, S.: New constructions of SSPDs and their applications. Comput. Geom. 45(5–6), 200–214 (2012)
Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. Discrete Comput. Geom. 41(4), 556–582 (2009)
Araújo, F., Rodrigues, L.: Fast localized Delaunay triangulation. In: Proceedings of the 8th International Conference on Principles of Distributed Systems, pp. 81–93 (2004)
Bae, S.W., Lee, C., Choi, S.: On exact solutions to the Euclidean bottleneck Steiner tree problem. Inf. Process. Lett. 110, 672–678 (2010)
Bespamyatnikh, S., Segal, M.: Fast algorithms for approximating distances. Algorithmica 33, 263–269 (2002)
Bollobás, B., Scott, A.: On separating systems. Eur. J. Comb. 28(4), 1068–1071 (2007)
Bose, P., Carmi, P., Smid, M., Xu, D.: Communication-efficient construction of the plane localized Delaunay graph. In: Proceedings LATIN, pp. 282–293 (2010)
Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42, 67–90 (1995)
Chan, T.: On enumerating and selecting distances. Int. J. Comput. Geom. Appl. 11(3), 291–304 (2001)
Chen, D., Du, D.-Z., Hu, X., Lin, G., Wang, L., Xue, G.: Approximations for Steiner trees with minimum number of Steiner points. J. Glob. Optim. 18, 17–33 (2000)
Cheng, X., Du, D.-Z., Wang, L., Xu, B.: Relay sensor placement in wireless sensor networks. Wirel. Netw. 14, 347–355 (2008)
Clarkson, K.L.: Approximation algorithms for shortest path motion planning. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC ’87), pp. 56–65 (1987)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)
de Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2008)
Frederickson, G.N., Johnson, D.B.: Generalized selection and ranking: sorted matrices. SIAM J. Comput. 13, 14–30 (1984)
Har-Peled, S., Raichel, B.A.: Net and prune: a linear time algorithm for Euclidean distance problems. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC ’13), pp. 605–614 (2013)
Hou, Y.-T., Chen, C.-M., Jeng, B.: An optimal new-node placement to enhance the coverage of wireless sensor networks. Wirel. Netw. 16, 1033–1043 (2010)
Huang, H., Richa, A.W., Segal, M.: Dynamic coverage in ad-hoc sensor networks. Mob. Netw. Appl. 10(1), 9–17 (2005)
Katz, M.J., Sharir, M.: An expander-based approach to geometric optimization. SIAM J. Comput. 26(5), 1384–1408 (1997)
Keil, J.M.: Approximating the complete Euclidean graph. In: Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT ’88). LNCS, vol. 318, pp. 208–213 (1988)
Li, X.-Y.: Wireless Ad Hoc and Sensor Networks: Theory and Applications. Cambridge University Press, Cambridge (2008)
Li, X.-Y., Calinescu, G., Wan, P.-J., Wang, Y.: Localized Delaunay triangulation with application in ad-hoc wireless networks. IEEE Trans. Parallel Distrib. Syst. 14(10), 1035–1047 (2003)
Li, Z.-M., Zhu, D.-M., Ma, S.-H.: Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane. J. Comput. Sci. Technol. 19(6), 791–794 (2004)
Lin, G.H., Xue, G.: Steiner tree problem with minimum number of Steiner points and bounded edge-length. Inf. Process. Lett. 69, 53–57 (1999)
Megerian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.B.: Worst and best-case coverage in sensor networks. IEEE Trans. Mob. Comput. 4(1), 84–92 (2005)
Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)
Roditty, L., Segal, M.: On bounded leg shortest path problems. Algorithmica 59, 583–600 (2011)
Varadarajan, K.R.: A divide-and-conquer algorithm for min-cost perfect matching in the plane. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’98), pp. 320–331 (1998)
Wang, L., Du, D.-Z.: Approximations for a bottleneck Steiner tree problem. Algorithmica 32, 554–561 (2002)
Wang, L., Li, Z.-M.: Approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane. Inf. Process. Lett. 81, 151–156 (2002)
Yao, A.C.: On constructing minimum spanning trees in k-dimensional space and related problems. SIAM J. Comput. 11(4), 721–736 (1982)