TY - JOUR

T1 - Space filling curves and mathematical programming

AU - Butz, Arthur R.

N1 - Funding Information:
1 This research was supported in part by the Joint Services Electronics Program (U.S. Navy), ONR Contract No. N00014-67-A-03564)003 and in part by NSF Grant No. GK-1540 to Northwestern University.

PY - 1968/4

Y1 - 1968/4

N2 - The problem of finding {if314-1} in n dimensional Euclidean space such that {if314-2}, i = 1, 2, ···, N, is considered. The only assumption on the fi is that a solution exists in the quantized unit hypercube. Implicitly exhaustive solution procedures, which obtain solutions by implicitly considering every point in the quantized space without making computations at each point, are studied. The implicitly exhaustive feature is made possible by adapting "space filling curves≓ to discrete spaces of general dimensionality. Several space filling curves are surveyed, and Peano's continuous mapping from the unit interval onto the unit square is used as a basis for defining a mapping from the unit quantized interval onto the unit quantized hypercube, and inversely. Ternary arithmetic is the basis for the required functional relationships in the discrete mapping. The discrete mapping has attributes of quasi-continuity, and specific numerical bounds are derived in this respect. It is shown that these bounds are of optimal order dependence on the relevant variables. It is shown how to use knowledge of first and second order properties of the fi to obtain solutions on a digital computer using space filling curves as a basis for the concept of implicitly exhaustive search. The only global properties assumed are bounds on first, or possibly second, order variations. Concluding remarks bear on the ultimate practicality of the method, and present a limited amount of experimental data.

AB - The problem of finding {if314-1} in n dimensional Euclidean space such that {if314-2}, i = 1, 2, ···, N, is considered. The only assumption on the fi is that a solution exists in the quantized unit hypercube. Implicitly exhaustive solution procedures, which obtain solutions by implicitly considering every point in the quantized space without making computations at each point, are studied. The implicitly exhaustive feature is made possible by adapting "space filling curves≓ to discrete spaces of general dimensionality. Several space filling curves are surveyed, and Peano's continuous mapping from the unit interval onto the unit square is used as a basis for defining a mapping from the unit quantized interval onto the unit quantized hypercube, and inversely. Ternary arithmetic is the basis for the required functional relationships in the discrete mapping. The discrete mapping has attributes of quasi-continuity, and specific numerical bounds are derived in this respect. It is shown that these bounds are of optimal order dependence on the relevant variables. It is shown how to use knowledge of first and second order properties of the fi to obtain solutions on a digital computer using space filling curves as a basis for the concept of implicitly exhaustive search. The only global properties assumed are bounds on first, or possibly second, order variations. Concluding remarks bear on the ultimate practicality of the method, and present a limited amount of experimental data.

UR - http://www.scopus.com/inward/record.url?scp=0001388605&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001388605&partnerID=8YFLogxK

U2 - 10.1016/S0019-9958(68)90367-7

DO - 10.1016/S0019-9958(68)90367-7

M3 - Article

AN - SCOPUS:0001388605

SN - 0019-9958

VL - 12

SP - 314

EP - 330

JO - Information and Control

JF - Information and Control

IS - 4

ER -