Share:


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

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

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
Published in Issue
Sep 24, 2018
Abstract Views
778
PDF Downloads
670
Creative Commons License

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