research-article

The euclidean bottleneck steiner path problem

Authors:

A. Karim Abu-Affash,

Matthew J. Katz,

Michael SegalAuthors Info & Claims

SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Pages 440 - 447

https://doi.org/10.1145/1998196.1998268

Published: 13 June 2011 Publication History

Abstract

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(n log² n)-time algorithm that computes an optimal solution, for any constant k. This problem was previously studied by Hou et al. [Hou10], who gave an O(n²log n)-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 W={(A₁,B₁),...,(A_m,B_m)} of pairs of subsets of P, satisfying: (i) For each pair (A_i,B_i) ∈ W, the radius of the minimum enclosing circle of A_i (resp. B_i) is at most α, and (ii) For any p,q ∈ P, such that |pq| ≤ β, there exists a single pair (A_i,B_i) ∈ 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((β/α)³ n log n).

Finally, for the complete graph with vertex set P and weight function w(p,q) = ⌊|pq|⌋, we construct a (1+ε)-spanner of size O(n/ε⁴) in time O((1/ε⁴)n log² n), even though w is not a metric.

References

[1]

M.A. Abam, M. de Berg, M. Farshi, and J. Gudmundsson. Region-fault tolerant geometric spanners. Discrete and Computational Geometry, 41(4):556--582, 2009.

Digital Library

[2]

S.W. Bae, C. Lee, and S. Choi. On exact solutions to the Euclidean bottleneck Steiner tree problem. Information Processing Letters, 110(16):672--678, 2010.

Digital Library

[3]

B. Bollobás and A. Scott. On separating systems. European Journal on Combinatorics, 28(4):1068--1071, 2007.

Digital Library

[4]

P.B. Callahan and S.R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM, 42:67--90, 1995.

Digital Library

[5]

D. Chen, D.-Z. Du, X. Hu, G Lin, L. Wang, and G. Xue. Approximations for Steiner trees with minimum number of Steiner points. Journal of Global Optimization, 18:17--33, 2000.

Digital Library

[6]

X. Cheng, D.-Z. Du, L. Wang, and B. Xu. Relay sensor placement in wireless sensor networks. Wireless Networks, 14:347--355, 2008.

Digital Library

[7]

K.L. Clarkson. Approximation algorithms for shortest path motion planning. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC '87), pages 56--65, 1987.

Digital Library

[8]

T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009.

Digital Library

[9]

M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications, 3rd Edition. Springer-Verlag, 2008.

Digital Library

[10]

G.N. Frederickson and D.B. Johnson. Generalized selection and ranking: Sorted matrices. SIAM Journal of Computing, 13:14--30, 1984.

[11]

Y.-T. Hou, C.-M. Chen, and B. Jeng. An optimal new-node placement to enhance the coverage of wireless sensor networks. Wireless Networks, 16:1033--1043, 2010.

Digital Library

[12]

H. Huang, A.W. Richa, and M. Segal. Dynamic coverage in ad-hoc sensor networks. Mobile Networks and Applications, 10(1):9--17, 2005.

Digital Library

[13]

J.M. Keil. Approximating the complete Euclidean graph. In Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT '88), volume 318 of LNCS, pages 208--213, 1988.

Digital Library

[14]

Z.-M. Li, D.-M. Zhu, and S.-H. Ma. Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane. Journal of Computer Science and Technology, 19(6):791--794, 2004.

Digital Library

[15]

G.H. Lin and G. Xue. Steiner tree problem with minimum number of Steiner points and bounded edge-length. Information Processing Letters, 69:53--57, 1999.

Digital Library

[16]

S. Megerian, F. Koushanfar, M. Potkonjak, and M.B. Srivastava. Worst and best-case coverage in sensor networks. IEEE Transactions on Mobile Computing, 4(1):84--92, 2005.

Digital Library

[17]

G. Narasimhan and M. Smid. Geometric Spanner Networks. Cambridge University Press, 2007.

Digital Library

[18]

K.R. Varadarajan. 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), pages 320--331, 1998.

Digital Library

[19]

L. Wang and D.-Z. Du. Approximations for a bottleneck Steiner tree problem. Algorithmica, 32:554--561, 2002.

Digital Library

[20]

L. Wang and Z.-M. Li. An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane. Information Processing Letters, 81(3):151--156, 2002.

Digital Library

Cited By

Mohanapriya APraveena CRenjith PSadagopan N(2020) Some Classical Problems on K 1,3 -free Split Graphs. 2020 IEEE 4th Conference on Information & Communication Technology (CICT)10.1109/CICT51604.2020.9312081(1-11)Online publication date: 3-Dec-2020
https://doi.org/10.1109/CICT51604.2020.9312081
Abu-Affash ACarmi PKatz M(2015)Bottleneck Steiner tree with bounded number of Steiner verticesJournal of Discrete Algorithms10.1016/j.jda.2014.12.00430:C(96-100)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.jda.2014.12.004

Index Terms

The euclidean bottleneck steiner path problem
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

The Euclidean Bottleneck Steiner Path Problem and Other Applications of (ź,β)-Pair Decomposition

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 ...
All-pairs bottleneck paths for general graphs in truly sub-cubic time
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

In the all-pairs bottleneck paths (APBP) problem (a.k.a. all-pairs maximum capacity paths), one is given a directed graph with real non-negative capacities on its edges and is asked to determine, for all pairs of vertices s and t, the capacity of a ...
Euclidean Steiner Shallow-Light Trees
SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

A spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree is called a shallow-light tree (shortly, SLT). More specifically, an (α, β)-SLT of a weighted undirected graph G = (V, E, w) with respect to a designated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

June 2011

532 pages

ISBN:9781450306829

DOI:10.1145/1998196

Program Chairs:
Ferran Hurtado
Universitat Politècnica de Catalunya
,
Marc van Kreveld
Utrecht University

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '11

Sponsor:

SoCG '11: Symposium on Computational Geometry

June 13 - 15, 2011

Paris, France

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
115
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mohanapriya APraveena CRenjith PSadagopan N(2020) Some Classical Problems on K 1,3 -free Split Graphs. 2020 IEEE 4th Conference on Information & Communication Technology (CICT)10.1109/CICT51604.2020.9312081(1-11)Online publication date: 3-Dec-2020
https://doi.org/10.1109/CICT51604.2020.9312081
Abu-Affash ACarmi PKatz M(2015)Bottleneck Steiner tree with bounded number of Steiner verticesJournal of Discrete Algorithms10.1016/j.jda.2014.12.00430:C(96-100)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.jda.2014.12.004

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents