Abstract: We will 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 in 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. We present an O(n log^2 n)-time algorithm that computes an optimal solution, for any constant k. This problem was previously studied by Hou et al.~\cite{Hou10}, who gave an O(n^2 logn)- time algorithm. We will also discuss the dual version of the problem, where a value \lambda > 0 is given, 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 \lambda. Our algorithms are based on two new geometric structures - an (\alpha,\beta)-pair decomposition of P and a floor (1+\eps)-spanner of P. For real numbers \beta > \alpha > 0, an (\alpha,\beta)-pair decomposition of P is a collection W={(A_1,B_1),...,(A_m,B_m)} of pairs of subsets of P, satisfying: (i) For each pair (A_i,B_i) \in W, the radius of the minimum enclosing circle of A_i (resp. B_i) is at most \alpha, and (ii) For any p,q \in P, such that |pq| \le \beta, there exists a single pair (A_i,B_i) \in W, such that p \in A_i and q \in B_i, or vice versa. Finally, for the complete graph with vertex set P and weight function w(p,q) = \lfloor |pq| \rfloor, we construct a (1+\eps)-spanner of size O(n/\eps^4), even though w is not a metric. Joint work with Paz Carmi, Matya Katz and Michael Segal