In this paper we address the problem of providing full connectivity in large (wide area) ad hoc networks by placing advantaged nodes like UAVs (as relay nodes) in appropriate places. We provide a formulation where we can treat the connectivity problem as a clustering problem with a summation-form distortion function. We then adapt the Deterministic Annealing clustering algorithm to our formulation and using that we nd the minimum number of UAVs required to provide connectivity and their locations. Furthermore, we describe enhancements that can be used to extend the basic connectivity problem to support notions of reliable connectivity that can lead to improved network performance. We establish the validity of our algorithm and compare its performance with optimal (exhaustive search) as well as non-opitmal (hard clustering) algorithms.We show that our algorithm is nearoptimal both for the basic connectivity problem as well as extended notions of connectivity.