Optimized Spatial Partitioning via Minimal Swarm Intelligence
This work addresses inefficiencies in spatial partitioning for applications like sensor networks and optimization, but it is incremental as it builds on existing CVT methods with modest enhancements.
The paper tackled the limitations of Centroidal Voronoi Tessellation (CVT) for spatial partitioning by proposing two simple schemes based on nearest and next nearest neighbor locations, which incorporate features like weighted regions and high-dimensional extension at a slight cost to optimal placement, and illustrated improvements in particle swarm optimizer results on multimodal test functions.
Optimized spatial partitioning algorithms are the corner stone of many successful experimental designs and statistical methods. Of these algorithms, the Centroidal Voronoi Tessellation (CVT) is the most widely utilized. CVT based methods require global knowledge of spatial boundaries, do not readily allow for weighted regions, have challenging implementations, and are inefficiently extended to high dimensional spaces. We describe two simple partitioning schemes based on nearest and next nearest neighbor locations which easily incorporate these features at the slight expense of optimal placement. Several novel qualitative techniques which assess these partitioning schemes are also included. The feasibility of autonomous uninformed sensor networks utilizing these algorithms are considered. Some improvements in particle swarm optimizer results on multimodal test functions from partitioned initial positions in two space are also illustrated. Pseudo code for all of the novel algorithms depicted here-in is available in the supplementary information of this manuscript.