Research On Capacity Constrained Centroidal Voronoi Tessellation And Its Application In Layout Problem

By imposing both centroid constraints and capacity constraints to ordinary Voronoi Tessellation, Capacity Constrained Centroidal Voronoi Tessellation (CCCVT) can generate Centroidal Voronoi Tessellation(CVT) with the capacity constraints, which is the research hotspot in the field of computational geometry. This dissertation presents a algorithm of CCCVT, and solves layout problems such as location and crowd distribution by applying it to model the continuous P-median and interpersonal bubble theory respectively.The main works of this dissertation are as follows:1) A algorithm of CCCVT is presented, which utilizes equality constraint to optimize capacity and uses L-BFGS to speed up the calculation on the basis of CVT algorithm. The proposed method has advantage of high efficiency and low error.2) CCCVT algorithm is used for modeling the continuous capacitated P-median problem in order to solve the layout problem of city emergency centers with dense demand. City population density function is fitted as density field, and then capacity constraint of each center is designated and CCCVT is introduced to perform optimization. Experiments and comparisons are conducted to prove the solution is valid and efficient.3) CCCVT algorithm is also used for modeling the interpersonal bubble theory to solve the crowd distribution problem. Interpersonal bubble theory is utilized to quantify the area of personal space for each individual, then CCCVT is introduced to tackle the crowd layout problem according to situation as homogeneous space, heterogeneous space and different density field, and finally visualization of results is conducted.4) A prototype system is constructed, and the proposed CCCVT algorithm is realized to accomplish the above layout problems.