The calculation of average distance in mesh structures

When solving problems in such areas as image processing, computer vision, and computational geometry, within a parallel architecture, the mesh structure often stands out as a natural choice. In this paper, we analyze a scalable measurement of the average distance between two arbitrary but fixed processors in a network structure, which is useful in providing a more global characterization of its data transmission behavior. In particular, we provide a closed-form expression for the average distance between two processors in the case of a traditional mesh. For a more complex case, where a traditional mesh is augmented with some additional diagonal links, after providing a telling expression for the average distance between its two processors, we prove that this latter expression cannot be represented in a closed-form format, with respect to a fairly general class of “standard operations”, namely, the class of the hypergeometric terms. Besides suggesting another global measurement of the communication behavior for general computer networks, and deriving concrete results for some “popular” mesh structures, this paper provides both positive and negative results regarding the derivation of closed-form expressions for combinatorial quantities, thus, is also theoretically interesting. We also believe that some of the general techniques used in this paper should be applicable elsewhere when closed-form expression needs to be derived, or its existence is in question.