Supported by research available of township system and influential sphere, the research is conducted based on towns in Bijie City, as per Voronoi diagram and breaking point theory. In the research, Shixi Office domina...Supported by research available of township system and influential sphere, the research is conducted based on towns in Bijie City, as per Voronoi diagram and breaking point theory. In the research, Shixi Office dominated as the highest center and Salaxi Town and Haizijie Town were sub-centers, supplemented by Yachi Town, Zhuchang Town, Yangjiawan Town, Qingchang Town, Heguantun Town, Qingshuipu Town, Yanzikou Town and Longchangying Town. Hence, township system and influ- ential sphere were determined and related methods and technologies were explored.展开更多
Based on the object oriented data structure of Voronoi diagram, the algorithm of the trimmed offset generating and the optimal too l path planning of the pocket machining for multiply connected polygonal domains are ...Based on the object oriented data structure of Voronoi diagram, the algorithm of the trimmed offset generating and the optimal too l path planning of the pocket machining for multiply connected polygonal domains are studied. The intersection state transition rule is improved in this algorithm. The intersection is between the trimmed offsets and Voronoi polygon. On this basis, the trimmed offset generating and the optimal tool path planning are mad e with three stacks(I stack, C stack and P stack)in different monotonous pouches of Voronoi diagram. At the same time, a merging method of Voronoi diagram an d offsets generating for multiply connected polygonal domains is also presented. The above algorithms have been implemented in NC machining successfully, and the efficiency is fully verified.展开更多
We consider a network of computer data centers on the earth surface delivering computing as a service to a big number of users. The problem is to assign users to data centers to minimize the total communication distan...We consider a network of computer data centers on the earth surface delivering computing as a service to a big number of users. The problem is to assign users to data centers to minimize the total communication distance between compu-ting resources and their users in the face of capacity constrained datacenters. In this paper, we extend the classical pla-nar Voronoi Diagram to a hyperbolic Voronoi Diagram on the sphere. We show that a solution to the distance minimi-zation problem under capacity constraints is given by a hyperbolic spherical Voronoi Diagram of data centers. We also present numerical algorithms, computer implementation and results of simulations illustrating our solution. We note applicability of our solution to other important assignment problems, including the assignment of population to regional trauma centers, location of airbases, the distribution of the telecommunication centers for mobile telephones in global telephone companies, and others.展开更多
The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space.In order to compensate the shortcomings of the existing methods,a directional ne...The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space.In order to compensate the shortcomings of the existing methods,a directional nearest neighbor query method in specific direction space based on Voronoi diagram is put forward.This work studies two cases,i.e.the query point is static and the query point moves with a constant velocity.Under the static condition,the corresponding pruning method and the pruning algorithm of the specified direction nearest neighbor(pruning_SDNN algorithm)are proposed by combining the plane right-angle coordinate system with the north-west direction,and then according to the smallest external rectangle of Voronoi polygon,the specific query is made and the direction nearest neighbor query based on Voronoi rectangle(VR-DNN) algorithm is given.In the case of moving with a constant velocity,first of all,the combination of plane right angle coordinate system,geographical direction and circle are used,the query range is determined and pruning methods and the pruning algorithm of the direction nearest neighbor based on decision circle(pruning_DDNN algorithm) are put forward.Then,according to the different position of motion trajectory and Voronoi diagram,a specific query through the nature of Voronoi diagram is given.At last,the direction nearest neighbor query based on Voronoi diagram and motion trajectory(VM-DNN) algorithm is put forward.The theoretical research and experiments show that the proposed algorithm can effectively deal with the problem of the nearest neighbor query for a specified geographical direction space.展开更多
Mobile-Edge Computing(MEC)displaces cloud services as closely as possible to the end user.This enables the edge servers to execute the offloaded tasks that are requested by the users,which in turn decreases the energy...Mobile-Edge Computing(MEC)displaces cloud services as closely as possible to the end user.This enables the edge servers to execute the offloaded tasks that are requested by the users,which in turn decreases the energy consumption and the turnaround time delay.However,as a result of a hostile environment or in catastrophic zones with no network,it could be difficult to deploy such edge servers.Unmanned Aerial Vehicles(UAVs)can be employed in such scenarios.The edge servers mounted on these UAVs assist with task offloading.For the majority of IoT applications,the execution times of tasks are often crucial.Therefore,UAVs tend to have a limited energy supply.This study presents an approach to offload IoT user applications based on the usage of Voronoi diagrams to determine task delays and cluster IoT devices dynamically as a first step.Second,the UAV flies over each cluster to perform the offloading process.In addition,we propose a Graphics Processing Unit(GPU)-based parallelization of particle swarm optimization to balance the cluster sizes and identify the shortest path along these clusters while minimizing the UAV flying time and energy consumption.Some evaluation results are given to demonstrate the effectiveness of the presented offloading strategy.展开更多
The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system ...The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system (GIS) has a collection of nearest neighborhood operations and this collection serves as a useful toolbox for spatial analysis. These operations are undertaken through the Voronoi diagrams. This paper presents a novel algorithm that constructs a' shortest route set' with respect to a given source point and a target point by Voronoi diagrams. It will help to improve the efficiency of traditional algorithms, e. g., Djkstra algorithm, on selecting the shortest routes. Moreover, the novel algorithm can check the connectivity in a complex network between the source point and target one.展开更多
A new heuristics model based on the Voronoi diagram is presented to simulate pedestrian dynamics with the noncrowded state, in which these mechanisms of preference demand evading and surpassing, microscopic anti-deadl...A new heuristics model based on the Voronoi diagram is presented to simulate pedestrian dynamics with the noncrowded state, in which these mechanisms of preference demand evading and surpassing, microscopic anti-deadlock, and site-fine-tuning are considered. The preference demand describes the willingness determination of detouring or following other pedestrians. In the evading and surpassing mechanisms, in order to achieve a balance between avoiding conflicts and minimizing detour distances, a new pair of concepts: "allow-areas and denial-areas" are introduced to divide the feasible region for pedestrians detour behaviors, in which the direction and magnitude of detour velocity are determined.A microscopic anti-deadlock mechanism is inserted to avoid deadlock problem of the counter-directional pedestrian. A site-fine-tuning mechanism is introduced to describe the behavior of avoiding getting too close to the neighbors in pedestrian movement. The presented model is verified through multiple scenarios, including the uni-or bi-direction pedestrian flow in the corridor without obstacles, the uni-direction pedestrian flow in the corridor with obstacles, and the pedestrian evacuation from a room with single-exit. The simulation results show that the velocity–density relationship is consistent with empirical data. Some self-organizing phenomena, such as lanes formation and arching are observed in the simulation.When pedestrians detour an obstacle, the avoiding area before the obstacle and the unoccupied area after the obstacle can be observed. When pedestrians evacuate through a bottleneck without panic, the fan-shaped crowd can be found, which is consistent with the actual observation. It is also found that the behavior of following others in an orderly manner is more conducive to the improvement of the overall movement efficiency when the crowd moves in a limited space.展开更多
The electric vehicle charging station should be allocated based on traffic density, geographical distribution and other factors, and Voronoi diagram is adopted to set the service area of charging station. In combinati...The electric vehicle charging station should be allocated based on traffic density, geographical distribution and other factors, and Voronoi diagram is adopted to set the service area of charging station. In combination with the actual situation of site selection of electric vehicle charging station, the comprehensive benefits index system is established. There are numerous factors influencing the site selection, among which there are uncertainty and fuzziness. The comprehensive evaluation method based on the fuzzy analysis and Analytical Hierarchy Process (AHP) is used to evaluate the comprehensive benefits in the site selection of electric vehicle charging stations, with the consultation of experts. This paper contributes to the best selection of comprehensive benefits and provides the reference for the decision-making of building the electric vehicle charging station. Actual examples show that the method proposed is effective.展开更多
Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the min...Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algo- rithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.展开更多
基金Supported by General Plan of Bijie Land Use ([2009]XY1015)~~
文摘Supported by research available of township system and influential sphere, the research is conducted based on towns in Bijie City, as per Voronoi diagram and breaking point theory. In the research, Shixi Office dominated as the highest center and Salaxi Town and Haizijie Town were sub-centers, supplemented by Yachi Town, Zhuchang Town, Yangjiawan Town, Qingchang Town, Heguantun Town, Qingshuipu Town, Yanzikou Town and Longchangying Town. Hence, township system and influ- ential sphere were determined and related methods and technologies were explored.
文摘Based on the object oriented data structure of Voronoi diagram, the algorithm of the trimmed offset generating and the optimal too l path planning of the pocket machining for multiply connected polygonal domains are studied. The intersection state transition rule is improved in this algorithm. The intersection is between the trimmed offsets and Voronoi polygon. On this basis, the trimmed offset generating and the optimal tool path planning are mad e with three stacks(I stack, C stack and P stack)in different monotonous pouches of Voronoi diagram. At the same time, a merging method of Voronoi diagram an d offsets generating for multiply connected polygonal domains is also presented. The above algorithms have been implemented in NC machining successfully, and the efficiency is fully verified.
文摘We consider a network of computer data centers on the earth surface delivering computing as a service to a big number of users. The problem is to assign users to data centers to minimize the total communication distance between compu-ting resources and their users in the face of capacity constrained datacenters. In this paper, we extend the classical pla-nar Voronoi Diagram to a hyperbolic Voronoi Diagram on the sphere. We show that a solution to the distance minimi-zation problem under capacity constraints is given by a hyperbolic spherical Voronoi Diagram of data centers. We also present numerical algorithms, computer implementation and results of simulations illustrating our solution. We note applicability of our solution to other important assignment problems, including the assignment of population to regional trauma centers, location of airbases, the distribution of the telecommunication centers for mobile telephones in global telephone companies, and others.
基金Supported by the National Natural Science Foundation of China(No.61872105,62072136)the Natural Science Foundation of Heilongjiang Province(No.LH2020F047)+1 种基金the Scientific Research Foundation for Returned Scholars Abroad of Heilongjiang Province of China(No.LC2018030)the National Key R&D Program of China(No.2020YFB1710200)。
文摘The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space.In order to compensate the shortcomings of the existing methods,a directional nearest neighbor query method in specific direction space based on Voronoi diagram is put forward.This work studies two cases,i.e.the query point is static and the query point moves with a constant velocity.Under the static condition,the corresponding pruning method and the pruning algorithm of the specified direction nearest neighbor(pruning_SDNN algorithm)are proposed by combining the plane right-angle coordinate system with the north-west direction,and then according to the smallest external rectangle of Voronoi polygon,the specific query is made and the direction nearest neighbor query based on Voronoi rectangle(VR-DNN) algorithm is given.In the case of moving with a constant velocity,first of all,the combination of plane right angle coordinate system,geographical direction and circle are used,the query range is determined and pruning methods and the pruning algorithm of the direction nearest neighbor based on decision circle(pruning_DDNN algorithm) are put forward.Then,according to the different position of motion trajectory and Voronoi diagram,a specific query through the nature of Voronoi diagram is given.At last,the direction nearest neighbor query based on Voronoi diagram and motion trajectory(VM-DNN) algorithm is put forward.The theoretical research and experiments show that the proposed algorithm can effectively deal with the problem of the nearest neighbor query for a specified geographical direction space.
基金funded by the University of Jeddah,Saudi Arabia,under Grant No.(UJ-20-102-DR).
文摘Mobile-Edge Computing(MEC)displaces cloud services as closely as possible to the end user.This enables the edge servers to execute the offloaded tasks that are requested by the users,which in turn decreases the energy consumption and the turnaround time delay.However,as a result of a hostile environment or in catastrophic zones with no network,it could be difficult to deploy such edge servers.Unmanned Aerial Vehicles(UAVs)can be employed in such scenarios.The edge servers mounted on these UAVs assist with task offloading.For the majority of IoT applications,the execution times of tasks are often crucial.Therefore,UAVs tend to have a limited energy supply.This study presents an approach to offload IoT user applications based on the usage of Voronoi diagrams to determine task delays and cluster IoT devices dynamically as a first step.Second,the UAV flies over each cluster to perform the offloading process.In addition,we propose a Graphics Processing Unit(GPU)-based parallelization of particle swarm optimization to balance the cluster sizes and identify the shortest path along these clusters while minimizing the UAV flying time and energy consumption.Some evaluation results are given to demonstrate the effectiveness of the presented offloading strategy.
文摘The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system (GIS) has a collection of nearest neighborhood operations and this collection serves as a useful toolbox for spatial analysis. These operations are undertaken through the Voronoi diagrams. This paper presents a novel algorithm that constructs a' shortest route set' with respect to a given source point and a target point by Voronoi diagrams. It will help to improve the efficiency of traditional algorithms, e. g., Djkstra algorithm, on selecting the shortest routes. Moreover, the novel algorithm can check the connectivity in a complex network between the source point and target one.
基金Project supported by the National Natural Science Foundation of China(Grant Nos.71771013 and 71621001)in part by the National Key Research and Development Program of China(Grant No.2019YFF0301403)+1 种基金in part by the Singapore Ministry of Education(MOE)Ac RF Tier 2(Grant No.MOE2016-T2-1-044)in part by the Fundamental Research Funds for the Central Universities,China(Grant NO.2019JBM041)。
文摘A new heuristics model based on the Voronoi diagram is presented to simulate pedestrian dynamics with the noncrowded state, in which these mechanisms of preference demand evading and surpassing, microscopic anti-deadlock, and site-fine-tuning are considered. The preference demand describes the willingness determination of detouring or following other pedestrians. In the evading and surpassing mechanisms, in order to achieve a balance between avoiding conflicts and minimizing detour distances, a new pair of concepts: "allow-areas and denial-areas" are introduced to divide the feasible region for pedestrians detour behaviors, in which the direction and magnitude of detour velocity are determined.A microscopic anti-deadlock mechanism is inserted to avoid deadlock problem of the counter-directional pedestrian. A site-fine-tuning mechanism is introduced to describe the behavior of avoiding getting too close to the neighbors in pedestrian movement. The presented model is verified through multiple scenarios, including the uni-or bi-direction pedestrian flow in the corridor without obstacles, the uni-direction pedestrian flow in the corridor with obstacles, and the pedestrian evacuation from a room with single-exit. The simulation results show that the velocity–density relationship is consistent with empirical data. Some self-organizing phenomena, such as lanes formation and arching are observed in the simulation.When pedestrians detour an obstacle, the avoiding area before the obstacle and the unoccupied area after the obstacle can be observed. When pedestrians evacuate through a bottleneck without panic, the fan-shaped crowd can be found, which is consistent with the actual observation. It is also found that the behavior of following others in an orderly manner is more conducive to the improvement of the overall movement efficiency when the crowd moves in a limited space.
文摘The electric vehicle charging station should be allocated based on traffic density, geographical distribution and other factors, and Voronoi diagram is adopted to set the service area of charging station. In combination with the actual situation of site selection of electric vehicle charging station, the comprehensive benefits index system is established. There are numerous factors influencing the site selection, among which there are uncertainty and fuzziness. The comprehensive evaluation method based on the fuzzy analysis and Analytical Hierarchy Process (AHP) is used to evaluate the comprehensive benefits in the site selection of electric vehicle charging stations, with the consultation of experts. This paper contributes to the best selection of comprehensive benefits and provides the reference for the decision-making of building the electric vehicle charging station. Actual examples show that the method proposed is effective.
基金Project supported by the National Nature Science Foundation of China (Nos. 60473103 and 60473127) and the Natural Science Foundation of Shandong Province (No. Y2005G03), China
文摘Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algo- rithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.
