Evaluation of pairwise distances among points forming a regular orthogonal grid in a hypercube

    Václav Sadílek   Affiliation
    ; Miroslav Vořechovský   Affiliation


Cartesian grid is a basic arrangement of points that form a regular orthogonal grid (ROG). In some applications, it is needed to evaluate all pairwise distances among ROG points. This paper focuses on ROG discretization of a unit hypercube of arbitrary dimension. A method for the fast enumeration of all pairwise distances and their counts for a high number of points arranged into high-dimensional ROG is presented. The proposed method exploits the regular and collapsible pattern of ROG to reduce the number of evaluated distances. The number of unique distances is identified and frequencies are determined using combinatorial rules. The measured computational speed-up compared to a naïve approach corresponds to the presented theoretical analysis. The proposed method and algorithm may find applications in various fields. The paper shows application focused on the behaviour of various distance measures with the motivation to find the lower bounds on the criteria of point distribution uniformity in Monte Carlo integration.

Keyword : full factorial design, design of experiments, pairwise distances, Audze-Eglãjs criterion, optimization, periodic space

How to Cite
Sadílek, V., & Vořechovský, M. (2018). Evaluation of pairwise distances among points forming a regular orthogonal grid in a hypercube. Journal of Civil Engineering and Management, 24(5), 410-423.
Published in Issue
Sep 24, 2018
Abstract Views
PDF Downloads
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.


Aggarwal, C. C.; Hinneburg, A.; Keim, D. A. 2001. On the surprising behavior of distance metrics in high dimensional space, in Proceedings of the 8th International Conference “Database Theory – ICDT 2001”, 4–6 January 2001, London, UK, 420–434.

Anderssen, R. S.; Brent, R. P.; Daley, D. J.; Moran, A. P. 1976. Concerning and a Taylor series method, SIAM Journal on Applied Mathematics 30: 22–30.

Audze, P.; Eglãjs, V. 1977. New approach for planning out of experiments, Problems of Dynamics and Strengths 35: 104–107.

Bailey, D. H.; Borwein, J. M.; Crandall, R. E. 2007. Box integrals, Journal of Computational and Applied Mathematics 206(1): 196–208.

Bates, S. J.; Sienz, J.; Langley, D. S. 2003. Formulation of the Audze–Eglais uniform Latin hypercube design of experiments, Advances in Engineering Software 34(8): 493–506.

Box, G. E. P. 1954. The exploration and exploitation of response surfaces: Some general considerations and examples, Biometrics 10(1): 16–60.

Bucher, C. G.; Bourgund, U. 1990. A fast and efficient response surface approach for structural reliability problems, Structural Safety 7(1): 57–66.

Chen, H.; Huang, H. Z.; Lin, D. K. J.; Liu, M. Q. 2016. Uniform sliced Latin hypercube designs, Applied Stochastic Models in Business and Industry 32: 574–584.

Chu, D. P. 2006. Distance between random points in two rectangular cities, Communications in Statistics – Simulation and Computation 35(2): 257–276.

Chudoba, R.; Sadílek, V.; Rypl, R.; Vořechovský, M. 2013. Using Python for scientific computing: an efficient and flexible evaluation of the statistical characteristics of functions with multivariate random inputs, Computer Physics Communications 184(2): 414–427.

Damblin, G.; Couplet, M.; Iooss, B. 2013. Numerical studies of space-filling designs: optimization of Latin Hypercube Samples and subprojection properties, Journal of Simulation 7(4): 276–289.

Eliáš, J.; Vořechovský, M. 2016. Modification of the Audze–Eglãjs criterion to achieve a uniform distribution of sampling points, Advances in Engineering Software 100: 82–96.

Fang, K.-T.; Ma, C.-X. 2001. Wrap-around L2-discrepancy of random sampling, Latin Hypercube and uniform designs, Journal of Complexity 17(4): 608–624.

Flexer, A.; Schnitzer, D. 2015. Choosing ℓp norms in high-dimensional spaces based on hub analysis, Neurocomputing 169: 281–287.

Fuerle, F.; Sienz, J. 2011. Formulation of the Audze–Eglais uniform Latin hypercube design of experiments for constrained design spaces, Advances in Engineering Software 42(9): 680–689.

Gates, D. J. 1985. Asymptotics of two integrals from optimization theory and geometric probability, Advances in Applied Probability 17(4): 908–910.

Ghosh, B. 1951. Random distances within a rectangle and between two rectangles, Bulletin of Calcutta Statistical Association 43: 17–24.

Gupta, S.; Manohar, C. S. 2004. An improved response surface method for the determination of failure probability and importance measures, Structural Safety 26(2): 123–139.

Hamzah, M. O.; Golchin, B.; Woodward, D. 2017. A quick approach for rheological evaluation of warm asphalt binders using response surface method, Journal of Civil Engineering and Management 23(4): 475–486.

Huang, H. Z.; Lin, D. K. J.; Liu, M. Q.; Yang, J. F. 2016. Computer experiments with both qualitative and quantitative variables, Technometrics 58: 495–507.

Husslage, B. G. M.; Rennen, G.; van Dam, E. R.; den Hertog, D. 2011. Space-filling Latin hypercube designs for computer experiments, Optimization and Engineering 12(4): 611–630.

Husslage, B. G. M. 2006. Maximin designs for computer experiments: PhD thesis. CentER, Tilburg University.
Iman, R. C.; Conover, W. J. 1980. Small sample sensitivity analysis techniques for computer models with an application to risk assessment, Communications in Statistics – Theory and Methods A9(361–926): 1749–1842.

Janouchová, E.; Kučerová, A. 2013. Competitive comparison of optimal designs of experiments for sampling-based sensitivity analysis, Computers & Structures 124: 47–60.

Johnson, M. E.; Moore, L. M.; Ylvisaker, D. 1990. Minimax and maximin distance designs, Journal of Statistical Planning and Inference 2: 131–148.

Kala, Z.; Valeš, J.; Jönsson, J. 2017. Random fields of initial out of straightness leading to column buckling, Journal of Civil Engineering and Management 23(7): 902–913.

Kong, D.; Lu, S.; Frantzich, H.; Lo, S. M. 2013. A method for linking safety factor to the target probability of failure in fire safety engineering, Journal of Civil Engineering and Management 19(sup1): S212–S221.

Kovalovs, A.; Rucevskis, S. 2011. Identification of elastic properties of composite plate, in Proceedings of Annual Conference on Functional Materials and Nanotechnologies – FM&NT, Vol. 23. IOP Publishing, Ltd.

Li, W. W.; Wu, C. F. J. 1997. Columnwise-pairwise algorithms with applications to the construction of supersaturated designs, Technometrics 39(2): 171–179.

Liao, K.-W.; Lu, H.-J.; Wang, C.-Y. 2015. A probabilistic evaluation of pier-scour potential in the Gaoping River Basin of Taiwan, Journal of Civil Engineering and Management 21(5): 637–653.

Liefvendahl, M.; Stocki, R. 2006. A study on algorithms for optimization of Latin hypercubes, Journal of Statistical Planning and Inference 136(9): 3231–3247.

Moltchanov, D. 2012. Distance distributions in random networks, Ad Hoc Networks 10(6): 1146–1166.

Montgomery, D. C. 2006. Design and analysis of experiments. 8th ed. John Wiley & Sons.

Morris, M. D.; Mitchell, T. J. 1995. Exploratory designs for computational experiments, Journal of Statistical Planning and Inference 43(3): 381–402.

Mortazavi, A.; Toğan, V.; Nuhoğlu, A. 2017. Weight minimization of truss structures with sizing and layout variables using integrated particle swarm optimizer, Journal of Civil Engineering and Management 23(8): 985–1001.

Niederreiter, H. 1992. Random number generation and Quasi-Monte Carlo methods. Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics.

OEIS. 2010. The on-line encyclopedia of integer sequences [online], [cited 16 September 2016]. Available from Internet:

Pronzato, L.; Müller, W. G. 2012. Design of computer experiments: space filling and beyond, Statistics and Computing 22(3): 681–701.

R Core Team. 2016. R: A language and environment for statistical computing. Vienna, Austria: R Foundation for Statistical Computing.

Robbins, D. P.; Bolis, T. S. 1978. Average distance between two points in a box, American Mathematical Monthly 85(4): 277–278.

Sacks, J.; Schiller, S. B.; Welch, W. J. 1989. Designs for computer experiments, Technometrics 31(1): 41–47.

Sadílek, V.; Vořechovský, M. 2017. ROG – Regular Orthogonal Grid [online], [cited 18 September 2018]. Available from Internet:

Siddiquea, N.; Adelib, H. 2016. Applications of gravitational search algorithm in engineering, Journal of Civil Engineering and Management 22(8): 981–990.

Strauss, A.; Wan-Wendner, R.; Vidovic, A.; Zambon, I.; Yu, Q.; Frangopol, D. M.; Bergmeister, K. 2017. Gamma prediction models for long-term creep deformations of prestressed concrete bridges, Journal of Civil Engineering and Management 23(6): 681–698.

Tobler, W. R. 1970. A computer movie simulating urban growth in the Detroit region, Economic Geography 46: 234–240.

Vahdatirad, M. J.; Bayat, M.; Andersen, L. V.; Ibsen, L. B. 2015. Probabilistic finite element stiffness of a laterally loaded monopile based on an improved asymptotic sampling method, Journal of Civil Engineering and Management 21(4): 503–513.

van Etten, J. 2012. gdistance: Distances and routes on geographical grids. Department of Mathematics, KTH, Stockholm, Sweden.
van Rossum, G.; Hettinger, R.; Diedrich, J. 1991. The Python programming language. Prentice Hall.

Vořechovský, M.; Novák, D. 2009. Correlation control in small sample Monte Carlo type simulations I: A Simulated Annealing approach, Probabilistic Engineering Mechanics 24(3): 452–462.

Vu, H. M.; Forth, J. P.; Dao, D. V.; Toropov, V. V. 2014. The use of optimisation for enhancing the development of a novel sustainable masonry unit, Applied Mathematical Modelling 38(3): 853–863.

Weisstein, E. W. (n.d.) Hypercube line picking [online], [cited 16 September 2016]. Available from Internet: