Spatial Partitioning: From Macro to Nano Scale
University of North Texas
Spatial partitioning is the process of dividing an n-dimensional space into non-overlapping sub-regions. This research aims to use spatial partitioning algorithms in two different problem domains: resource distribution for emergency response plans and compositional analysis of alloys.
For optimal distribution of prophylactics during a bio-emergency, locations of ad-hoc clinics or service centers need to be identified and the population demand needs to be distributed between them such that the entire affected population is served as soon as possible and demand constraints at the clinics are satisfied. For the scenario in which locations of the ad-hoc clinics are already known, we present a novel greedy heuristic algorithm to balance the demand across the facilities. If the locations are not known, then the problem is translated into a p-median problem and solved using existing heuristic or meta-heuristic, which is selected based on the input parameters.
In the second problem, we aim to use spatial partitioning algorithms to analyze the atomic composition of alloys. The properties exhibited by alloys are dictated by the concentration, type, and arrangement of atoms in the material. A new binning algorithm, the Uniform Partitioning Algorithm(UPA) is proposed to perform frequency distribution analyses and detect heterogeneities in the material. UPA is shown to be more efficient in capturing spatial correlations than existing algorithms.
This research demonstrates various algorithms to store and manipulate two and three-dimensional spatial data. These methods are being used to assist public health planners to create feasible emergency response plans, and material scientists to establish correlations between microstructures in materials and their functional/physical properties.