Evaluation of pairwise distances among points forming a regular orthogonal grid in a hypercube
Abstract
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. https://doi.org/10.3846/jcem.2018.5189
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
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. https://doi.org/10.1007/3-540-44503-X_27
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. https://doi.org/10.1137/0130003
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. https://doi.org/10.1016/j.cam.2006.06.010
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. https://doi.org/10.1016/S0965-9978(03)00042-5
Box, G. E. P. 1954. The exploration and exploitation of response surfaces: Some general considerations and examples, Biometrics 10(1): 16–60. https://doi.org/10.2307/3001663
Bucher, C. G.; Bourgund, U. 1990. A fast and efficient response surface approach for structural reliability problems, Structural Safety 7(1): 57–66. https://doi.org/10.1016/0167-4730(90)90012-E
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. https://doi.org/10.1002/asmb.2192
Chu, D. P. 2006. Distance between random points in two rectangular cities, Communications in Statistics – Simulation and Computation 35(2): 257–276. https://doi.org/10.1080/03610910600591818
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. https://doi.org/10.1016/j.cpc.2012.08.021
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. https://doi.org/10.1057/jos.2013.16
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. https://doi.org/10.1016/j.advengsoft.2016.07.004
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. https://doi.org/10.1006/jcom.2001.0589
Flexer, A.; Schnitzer, D. 2015. Choosing ℓp norms in high-dimensional spaces based on hub analysis, Neurocomputing 169: 281–287. https://doi.org/10.1016/j.neucom.2014.11.084
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. https://doi.org/10.1016/j.advengsoft.2011.05.004
Gates, D. J. 1985. Asymptotics of two integrals from optimization theory and geometric probability, Advances in Applied Probability 17(4): 908–910. https://doi.org/10.1017/S0001867800015470
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. https://doi.org/10.1016/S0167-4730(03)00021-3
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. https://doi.org/10.3846/13923730.2016.1210216
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. https://doi.org/10.1080/00401706.2015.1094416
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. https://doi.org/10.1007/s11081-010-9129-8
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. https://doi.org/10.1016/j.compstruc.2013.04.009
Johnson, M. E.; Moore, L. M.; Ylvisaker, D. 1990. Minimax and maximin distance designs, Journal of Statistical Planning and Inference 2: 131–148. https://doi.org/10.1016/0378-3758(90)90122-B
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. https://doi.org/10.3846/13923730.2017.1341957
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. https://doi.org/10.3846/13923730.2013.802718
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. https://doi.org/10.1088/1757-899X/23/1/012034
Li, W. W.; Wu, C. F. J. 1997. Columnwise-pairwise algorithms with applications to the construction of supersaturated designs, Technometrics 39(2): 171–179. https://doi.org/10.2307/1270905
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. https://doi.org/10.3846/13923730.2014.890650
Liefvendahl, M.; Stocki, R. 2006. A study on algorithms for optimization of Latin hypercubes, Journal of Statistical Planning and Inference 136(9): 3231–3247. https://doi.org/10.1016/j.jspi.2005.01.007
Moltchanov, D. 2012. Distance distributions in random networks, Ad Hoc Networks 10(6): 1146–1166. https://doi.org/10.1016/j.adhoc.2012.02.005
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. https://doi.org/10.1016/0378-3758(94)00035-T
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. https://doi.org/10.3846/13923730.2017.1348982
Niederreiter, H. 1992. Random number generation and Quasi-Monte Carlo methods. Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611970081
OEIS. 2010. The on-line encyclopedia of integer sequences [online], [cited 16 September 2016]. Available from Internet: http://oeis.org
Pronzato, L.; Müller, W. G. 2012. Design of computer experiments: space filling and beyond, Statistics and Computing 22(3): 681–701. https://doi.org/10.1007/s11222-011-9242-3
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. https://doi.org/10.2307/2321177
Sacks, J.; Schiller, S. B.; Welch, W. J. 1989. Designs for computer experiments, Technometrics 31(1): 41–47. https://doi.org/10.1080/00401706.1989.10488474
Sadílek, V.; Vořechovský, M. 2017. ROG – Regular Orthogonal Grid [online], [cited 18 September 2018]. Available from Internet: https://github.com/kelidas/ROG
Siddiquea, N.; Adelib, H. 2016. Applications of gravitational search algorithm in engineering, Journal of Civil Engineering and Management 22(8): 981–990. https://doi.org/10.3846/13923730.2016.1232306
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. https://doi.org/10.3846/13923730.2017.1335652
Tobler, W. R. 1970. A computer movie simulating urban growth in the Detroit region, Economic Geography 46: 234–240. https://doi.org/10.2307/143141
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. https://doi.org/10.3846/13923730.2014.890660
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. https://doi.org/10.1016/j.probengmech.2009.01.004
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. https://doi.org/10.1016/j.apm.2013.07.026
Weisstein, E. W. (n.d.) Hypercube line picking [online], [cited 16 September 2016]. Available from Internet: http://mathworld.wolfram.com/HypercubeLinePicking.html
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. https://doi.org/10.1137/0130003
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. https://doi.org/10.1016/j.cam.2006.06.010
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. https://doi.org/10.1016/S0965-9978(03)00042-5
Box, G. E. P. 1954. The exploration and exploitation of response surfaces: Some general considerations and examples, Biometrics 10(1): 16–60. https://doi.org/10.2307/3001663
Bucher, C. G.; Bourgund, U. 1990. A fast and efficient response surface approach for structural reliability problems, Structural Safety 7(1): 57–66. https://doi.org/10.1016/0167-4730(90)90012-E
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. https://doi.org/10.1002/asmb.2192
Chu, D. P. 2006. Distance between random points in two rectangular cities, Communications in Statistics – Simulation and Computation 35(2): 257–276. https://doi.org/10.1080/03610910600591818
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. https://doi.org/10.1016/j.cpc.2012.08.021
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. https://doi.org/10.1057/jos.2013.16
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. https://doi.org/10.1016/j.advengsoft.2016.07.004
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. https://doi.org/10.1006/jcom.2001.0589
Flexer, A.; Schnitzer, D. 2015. Choosing ℓp norms in high-dimensional spaces based on hub analysis, Neurocomputing 169: 281–287. https://doi.org/10.1016/j.neucom.2014.11.084
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. https://doi.org/10.1016/j.advengsoft.2011.05.004
Gates, D. J. 1985. Asymptotics of two integrals from optimization theory and geometric probability, Advances in Applied Probability 17(4): 908–910. https://doi.org/10.1017/S0001867800015470
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. https://doi.org/10.1016/S0167-4730(03)00021-3
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. https://doi.org/10.3846/13923730.2016.1210216
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. https://doi.org/10.1080/00401706.2015.1094416
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. https://doi.org/10.1007/s11081-010-9129-8
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. https://doi.org/10.1016/j.compstruc.2013.04.009
Johnson, M. E.; Moore, L. M.; Ylvisaker, D. 1990. Minimax and maximin distance designs, Journal of Statistical Planning and Inference 2: 131–148. https://doi.org/10.1016/0378-3758(90)90122-B
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. https://doi.org/10.3846/13923730.2017.1341957
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. https://doi.org/10.3846/13923730.2013.802718
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. https://doi.org/10.1088/1757-899X/23/1/012034
Li, W. W.; Wu, C. F. J. 1997. Columnwise-pairwise algorithms with applications to the construction of supersaturated designs, Technometrics 39(2): 171–179. https://doi.org/10.2307/1270905
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. https://doi.org/10.3846/13923730.2014.890650
Liefvendahl, M.; Stocki, R. 2006. A study on algorithms for optimization of Latin hypercubes, Journal of Statistical Planning and Inference 136(9): 3231–3247. https://doi.org/10.1016/j.jspi.2005.01.007
Moltchanov, D. 2012. Distance distributions in random networks, Ad Hoc Networks 10(6): 1146–1166. https://doi.org/10.1016/j.adhoc.2012.02.005
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. https://doi.org/10.1016/0378-3758(94)00035-T
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. https://doi.org/10.3846/13923730.2017.1348982
Niederreiter, H. 1992. Random number generation and Quasi-Monte Carlo methods. Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611970081
OEIS. 2010. The on-line encyclopedia of integer sequences [online], [cited 16 September 2016]. Available from Internet: http://oeis.org
Pronzato, L.; Müller, W. G. 2012. Design of computer experiments: space filling and beyond, Statistics and Computing 22(3): 681–701. https://doi.org/10.1007/s11222-011-9242-3
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. https://doi.org/10.2307/2321177
Sacks, J.; Schiller, S. B.; Welch, W. J. 1989. Designs for computer experiments, Technometrics 31(1): 41–47. https://doi.org/10.1080/00401706.1989.10488474
Sadílek, V.; Vořechovský, M. 2017. ROG – Regular Orthogonal Grid [online], [cited 18 September 2018]. Available from Internet: https://github.com/kelidas/ROG
Siddiquea, N.; Adelib, H. 2016. Applications of gravitational search algorithm in engineering, Journal of Civil Engineering and Management 22(8): 981–990. https://doi.org/10.3846/13923730.2016.1232306
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. https://doi.org/10.3846/13923730.2017.1335652
Tobler, W. R. 1970. A computer movie simulating urban growth in the Detroit region, Economic Geography 46: 234–240. https://doi.org/10.2307/143141
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. https://doi.org/10.3846/13923730.2014.890660
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. https://doi.org/10.1016/j.probengmech.2009.01.004
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. https://doi.org/10.1016/j.apm.2013.07.026
Weisstein, E. W. (n.d.) Hypercube line picking [online], [cited 16 September 2016]. Available from Internet: http://mathworld.wolfram.com/HypercubeLinePicking.html