Weight-proportional space partitioning using adaptive Voronoi diagrams

作者：Reitsma Rene^*; Trubin Stanislav; Mortensen Eric

来源：GeoInformatica, 2007, 11(3): 383-405.

DOI：10.1007/s10707-006-0006-8

• information space
• space partitioning
• Voronoi diagrams
• adaptive algorithm
• area-weight proportional
• fixed-point iteration
• quadtree decomposition
• optimization
• spatial resolution
• algorithm complexity

Traditional application of Voronoi diagrams for space partitioning results in Voronoi regions, each with a specific area determined by the generators' relative locations and weights. Particularly in the area of information space (re)construction, however, there is a need for inverse solutions; i.e., finding weights that result in regions with predefined area ratios. In this paper, we formulate an adaptive Voronoi solution and propose a raster-based optimization method for finding the associated weight set. The solution consists of a combination of simple, fixed-point iteration with an optional spatial resolution refinement along the regions' boundaries using quadtree decomposition. We present the corresponding algorithm and its complexity analysis. The method is successfully tested on a series of ideal-typical cases and the interactions between the adaptive technique and boundary resolution refinement are explored and assessed.

• 出版日期2007-9