Journal articles: 'Additively Weighted Voronoi Diagram'

1

Kim, Jae-Kwan, Youngsong Cho, Donguk Kim, and Deok-Soo Kim. "Voronoi diagrams, quasi-triangulations, and beta-complexes for disks in R2: the theory and implementation in BetaConcept." Journal of Computational Design and Engineering 1, no. 2 (April 1, 2014): 79–87. http://dx.doi.org/10.7315/jcde.2014.008.

Full text

Abstract:

Abstract Voronoi diagrams are powerful for solving spatial problems among particles and have been used in many disciplines of science and engineering. In particular, the Voronoi diagram of three-dimensional spheres, also called the additively-weighted Voronoi diagram, has proven its powerful capabilities for solving the spatial reasoning problems for the arrangement of atoms in both molecular biology and material sciences. In order to solve application problems, the dual structure, called the quasi-triangulation, and its derivative structure, called the beta-complex, are frequently used with the Voronoi diagram itself. However, the Voronoi diagram, the quasi-triangulation, and the beta-complexes are sometimes regarded as somewhat difficult for ordinary users to understand. This paper presents the twodimensional counterparts of their definitions and introduce the BetaConcept program which implements the theory so that users can easily learn the powerful concept and capabilities of these constructs in a plane. The BetaConcept program was implemented in the standard C++ language with MFC and OpenGL and freely available at Voronoi Diagram Research Center (http://voronoi.hanyang.ac.kr).

APA, Harvard, Vancouver, ISO, and other styles

2

DE LACY COSTELLO, B. P. J., I. JAHAN, P. HAMBIDGE, K. LOCKING, D. PATEL, and A. ADAMATZKY. "CHEMICAL TESSELLATIONS — RESULTS OF BINARY AND TERTIARY REACTIONS BETWEEN METAL IONS AND FERRICYANIDE OR FERROCYANIDE LOADED GELS." International Journal of Bifurcation and Chaos 20, no. 07 (July 2010): 2241–52. http://dx.doi.org/10.1142/s0218127410027064.

Full text

Abstract:

In our recent letter [de Lacy Costello et al., 2009] we described the formation of spontaneous complex tessellations of the plane constructed in simple chemical reactions between drops of metal salts and ferricyanide or ferrocyanide loaded gels. In this paper, we provide more examples of binary tessellations and extend our analysis to tessellations constructed via tertiary mixtures of reactants. We also provide a classification system which describes the tessellation based on the reactivity of the metal salt with the substrate and also the cross-reactivity of the primary products. This results in balanced tessellations where both reactants have equal reactivity or unbalanced tessellations where one reactant has a lower reactivity with the gel. The products can also be partially or fully cross reactive which gives a highly complex tessellation. The tessellations are made up of colored cells (corresponding to different metal ferricyanides or ferrocyanides) separated by bisectors of low precipitate concentration. The tessellations constructed by these reactions constitute generalized Voronoi diagrams. In the case of certain binary or tertiary combinations of reactants where the diffusion/reaction rates differ, then multiplicatively weighted crystal growth Voronoi diagrams are constructed. Where one reactant has limited or no reactivity with the gel (or the products are cross reactive) then the fronts originating from the reactive metal ions cross the fronts originating from the partially reactive metal ions. The fronts can annihilate in the formation of a second Voronoi diagram relating to the relative positions of the reactive drops. Therefore, two or more generalised or weighted Voronoi diagrams can be calculated in parallel by these simple chemical systems. However when these reactions were used to calculate an additively weighted Voronoi diagram (the reaction was initiated at different time intervals) the diagram constructed did not correspond to the theoretical calculation. We use the failure of these reactions to construct an additively weighted Voronoi diagram to prove a mechanism of substrate competition for bisector formation. These tessellations are an important class of pattern forming reactions and are useful in modeling natural pattern forming phenomena in addition to being a great resource for scientific demonstrations.

APA, Harvard, Vancouver, ISO, and other styles

3

Manak, M. "Exploration of Empty Space among Spherical Obstacles via Additively Weighted Voronoi Diagram." Computer Graphics Forum 35, no. 5 (August 2016): 249–58. http://dx.doi.org/10.1111/cgf.12980.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

De Lacy Costello, Ben. "Calculating Voronoi Diagrams Using Simple Chemical Reactions." Parallel Processing Letters 25, no. 01 (March 2015): 1540003. http://dx.doi.org/10.1142/s0129626415400034.

Full text

Abstract:

This paper overviews work on the use of simple chemical reactions to calculate Voronoi diagrams and undertake other related geometric calculations. This work highlights that this type of specialised chemical processor is a model example of a parallel processor. For example increasing the complexity of the input data within a given area does not increase the computation time. These processors are also able to calculate two or more Voronoi diagrams in parallel. Due to the specific chemical reactions involved and the relative strength of reaction with the substrate (and cross-reactivity with the products) these processors are also capable of calculating Voronoi diagrams sequentially from distinct chemical inputs. The chemical processors are capable of calculating a range of generalised Voronoi diagrams (either from circular drops of chemical or other geometric shapes made from adsorbent substrates soaked in reagent) , skeletonisation of planar shapes and weighted Voronoi diagrams (e.g., additively weighted Voronoi diagrams, Multiplicitavely weighted Crystal growth Voronoi diagrams). The paper will also discuss some limitations of these processors. These chemical processors constitute a class of pattern forming reactions which have parallels with those observed in natural systems. It is possible that specialised chemical processors of this general type could be useful for synthesising functional structured materials.

APA, Harvard, Vancouver, ISO, and other styles

5

Papatheodorou, Sotiris, Anthony Tzes, Konstantinos Giannousakis, and Yiannis Stergiopoulos. "Distributed area coverage control with imprecise robot localization." International Journal of Advanced Robotic Systems 15, no. 5 (September 1, 2018): 172988141879749. http://dx.doi.org/10.1177/1729881418797494.

Full text

Abstract:

This article examines the static area coverage problem by a network of mobile, sensor-equipped agents with imprecise localization. Each agent has uniform radial sensing ability and is governed by first-order kinodynamics. To partition the region of interest, a novel partitioning scheme, the Additively Weighted Guaranteed Voronoi diagram is introduced which takes into account both the agents’ positioning uncertainty and their heterogeneous sensing performance. Each agent’s region of responsibility corresponds to its Additively Weighted Guaranteed Voronoi cell, bounded by hyperbolic arcs. An appropriate gradient ascent-based control scheme is derived so that it guarantees monotonic increase of a coverage objective and is extended with collision avoidance properties. Additionally, a computationally efficient simplified control scheme is offered that is able to achieve comparable performance. Several simulation studies are offered to evaluate the performance of the two control schemes. Finally, two experiments using small differential drive-like robots and an ultra-wideband positioning system were conducted, highlighting the performance of the proposed control scheme in a real world scenario.

APA, Harvard, Vancouver, ISO, and other styles

6

Moreno-Regidor, Pilar, Jésus García López de Lacalle, and Miguel-Ángel Manso-Callejo. "Zone design of specific sizes using adaptive additively weighted Voronoi diagrams." International Journal of Geographical Information Science 26, no. 10 (October 2012): 1811–29. http://dx.doi.org/10.1080/13658816.2012.655742.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Charalampopoulos, Panagiotis, Paweł Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, and Christian Wulff-Nilsen. "Almost Optimal Exact Distance Oracles for Planar Graphs." Journal of the ACM 70, no. 2 (March 25, 2023): 1–50. http://dx.doi.org/10.1145/3580474.

Full text

Abstract:

We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q , and since the mid-1990s all results had polynomial time-space tradeoffs, e.g., Q = ~ Θ( n/√ S ) or Q = ~Θ( n 5/2 /S 3/2 ). In this article we show that there is no polynomial tradeoff between time and space and that it is possible to simultaneously achieve almost optimal space n 1+ o (1) and almost optimal query time n o (1) . More precisely, we achieve the following space-time tradeoffs: n 1+ o (1) space and log 2+ o (1) n query time, n log 2+ o (1) n space and n o (1) query time, n 4/3+ o (1) space and log 1+ o (1) n query time. We reduce a distance query to a variety of point location problems in additively weighted Voronoi diagrams and develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures.

APA, Harvard, Vancouver, ISO, and other styles

8

Kaplan, Haim, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. "Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications." Discrete & Computational Geometry 64, no. 3 (September 22, 2020): 838–904. http://dx.doi.org/10.1007/s00454-020-00243-7.

Full text

Abstract:

Abstract We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $$L_p$$ L p -norms and additively weighted Euclidean distances. Our data structure supports general (convex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses $$O(n \log ^3 n)$$ O ( n log 3 n ) storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat, and Sharir which required $$O(n^{\varepsilon })$$ O ( n ε ) time for an update and $$O(\log n)$$ O ( log n ) time for a query [SICOMP 1999]. Our data structure has numerous applications. In all of them, it gives faster algorithms, typically reducing an $$O(n^{\varepsilon })$$ O ( n ε ) factor in the previous bounds to polylogarithmic. In addition, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques from the literature. Along the way, we obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for computing the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest-neighbor context, under both types of norm). To analyze this algorithm, we also improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we combine our vertical shallow cutting construction with Chan’s algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in $${{\mathbb {R}}}^3$$ R 3 . Along the way, we also revisit Chan’s technique and present a variant that uses a single binary counter, with a simpler analysis and improved amortized deletion time (by a logarithmic factor; the insertion and query costs remain asymptotically the same).

APA, Harvard, Vancouver, ISO, and other styles

9

Aurenhammer, Franz. "The one-dimensional weighted voronoi diagram." Information Processing Letters 22, no. 3 (March 1986): 119–23. http://dx.doi.org/10.1016/0020-0190(86)90055-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

HERMANTO, MELINDA, TJOKORDA BAGUS OKA, and I. PUTU EKA NILA KENCANA. "PENENTUAN LOKASI SMA NEGERI MENGGUNAKAN DIAGRAM VORONOI BERBOBOT DI KOTA DENPASAR." E-Jurnal Matematika 2, no. 2 (May 31, 2013): 27. http://dx.doi.org/10.24843/mtk.2013.v02.i02.p034.

Full text

Abstract:

In school development problem, determining location is one of important things to consider. In this research, the purpose is to determine the location of SMAN 9 Denpasar if it will be built. One of algorithms in computational geometry that can be used to find solution of facility location problem is multiplicatively weighted Voronoi diagram in two dimensions. The result of weighted Voronoi diagram shows the influence of each site to the surrounding area. Then, the location of SMAN 9 Denpasar is obtained by determining the center of the largest empty circle of the weighted Voronoi diagram.

APA, Harvard, Vancouver, ISO, and other styles

11

Kang, Shun. "A Generic Statistics-Based Tessellation Method of Voronoi Diagram." Journal of Systems Science and Information 3, no. 6 (December 25, 2015): 568–76. http://dx.doi.org/10.1515/jssi-2015-0568.

Full text

Abstract:

AbstractIn terms of distance function and spatial continuity in Voronoi diagram, a generic generating method of Voronoi diagram, named statistical Voronoi diagram, is proposed in this paper based upon statistics with mean vector and covariance matrix. Besides, in order to make good on the discreteness of spatial Voronoi cell, the cross Voronoi cell accomplished the discrete ranges in its continuous domain. In the light of Mahalanobis distance, not only ordinary Voronoi and weighted Voronoi are implemented, but also the theory of Voronoi diagram is improved further. Last but not least, through Gaussian distribution on spatial data, the validation and soundness of this method are proofed by empirical results.

APA, Harvard, Vancouver, ISO, and other styles

12

Miao, Pei Qing, Qi Bin Meng, Yue Li, and Qing Bo Tu. "Optimal Substation Locating and Sizing Based on Improved Weighted Voronoi Diagram and Genetic Algorithm." Applied Mechanics and Materials 644-650 (September 2014): 3515–21. http://dx.doi.org/10.4028/www.scientific.net/amm.644-650.3515.

Full text

Abstract:

Optimal planning of substation locating and sizing is one of the major components of distribution system planning projects. In this paper an approach for optimal locating, sizing and determining the power supply areas of substations using Improved Weighted Voronoi Diagram and Genetic Algorithm (WVD-GA) is presented. For rational power supply areas, variable weights and fixed weights are introduced as new concepts of weighted voronoi diagram to adjust the weights dynamically by considering substation characteristics and load density distribution. And an algorithm based on Cellular Automata (CA) for creating weighted voronoi diagram is designed, which greatly improve the performance of the creating process. The results show the efficiency and capability of the proposed method.

APA, Harvard, Vancouver, ISO, and other styles

13

Wang, Hui. "Discrete Construction of Compoundly Weighted Voronoi Diagram." Applied Mechanics and Materials 467 (December 2013): 545–48. http://dx.doi.org/10.4028/www.scientific.net/amm.467.545.

Full text

Abstract:

Compoundly weighted Voronoi diagram is difficult to construct because the bisector is fairly complex. In traditional algorithm, production process is always extremely complex and it is more difficult to graphic display because of the complex definition of mathematic formula. In this paper, discrete algorithms are used to construct compoundly weighted Voronoi diagrams. The algorithm can get over all kinds of shortcomings that we have just mentioned. So it is more useful and effective than the traditional algorithm. The results show that the algorithm is both simple and useful, and it is of high potential value in practice.

APA, Harvard, Vancouver, ISO, and other styles

14

Wu, Xiao Yong, Yi Fan Zhu, and Tao Jing. "The Algorithm of Points Set Extracting from 2D Voronoi Diagram Based on Crystal Growth." Applied Mechanics and Materials 130-134 (October 2011): 2249–52. http://dx.doi.org/10.4028/www.scientific.net/amm.130-134.2249.

Full text

Abstract:

The outputs of constructing voronoi diagram with crystal growth algorithm are pixel points set. A whole methodology of extraction of pixel points set is introduced and magnifier scanning algorithm (MSA) which is used to identifying voronoi vertexes and edges is explained in detail. Experiments show that the methodology and MSA is clear and accurate to weighted voronoi diagram.

APA, Harvard, Vancouver, ISO, and other styles

15

Mu, Lan. "Polygon Characterization With the Multiplicatively Weighted Voronoi Diagram*." Professional Geographer 56, no. 2 (May 1, 2004): 223–39. http://dx.doi.org/10.1111/j.0033-0124.2004.05602007.x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Zhang, Yi Bin, Gang Wu, Wen Xiu Peng, and Yan Ru Chen. "Definition of the Logistics Park Hinterland Based on Weighted Voronoi Diagram." Applied Mechanics and Materials 253-255 (December 2012): 1503–7. http://dx.doi.org/10.4028/www.scientific.net/amm.253-255.1503.

Full text

Abstract:

Accurately defining the radiation scope of the logistics park is the basis of the rational planning of the logistics park as well as further improvement of the regional logistics efficiency, but currently there is still a lack of scientific and systematical theory focusing on the research of defining the radiation scope of the logistics park. Therefore the concept of ‘hinterland’ was introduced into the research of the radiation scope of the logistics park, and the concept of ‘logistics park hinterland’ was particularly proposed. Subsequently, based on the Voronoi diagram theory in computational geometry which reflects the advantage of the continuity of space division, and by introducing the ‘scale’ parameter in the breaking-point model into weighted Voronoi diagram, the model based on weighted Voronoi diagram to define the logistics park hinterland was built. Finally, this model was practically applied to the planning example of ‘Four logistics centers’ of Chengdu, and also by means of GIS software the respective hinterlands of ‘Four logistics centers’ of Chengdu were defined. It practically proves that this model overcomes the shortcomings existing in the conventional single space division theories and methods such as the breaking-point model and the ordinary Voronoi diagram theory, which makes the definition of the logistics park hinterland more reasonable and scientific.

APA, Harvard, Vancouver, ISO, and other styles

17

Wang, Minghua, Ran Ou, and Yan Wang. "Multiplicatively weighted Voronoi-based sensor collaborative redeployment in software-defined wireless sensor networks." International Journal of Distributed Sensor Networks 18, no. 3 (March 2022): 155014772110699. http://dx.doi.org/10.1177/15501477211069903.

Full text

Abstract:

Large-scale deployment of mobile wireless sensor networks has been widely used in some dangerous and hostile urban security surveillance scenarios. As a new network architecture, software-defined networks was introduced into wireless sensor networks to form a new software-defined wireless sensor networks to solve the problem of balanced large-scale deployment of sensor networks and simplify the complexity of network management. In this article, we first develop an original confident information coverage–based multiplicatively weighted Voronoi diagram through sensor clustering and sensor collaborative sensing. And then, we propose two sensor collaborative redeployment algorithms based on the novel confident information coverage–based multiplicatively weighted Voronoi diagram and software-defined wireless sensor networks architecture to provide high-confidence coverage and improve the coverage ratio. Finally, we demonstrate the superiority of the confident information coverage–based multiplicatively weighted Voronoi diagram and the effectiveness and efficiency of our proposed algorithms via a series of experiments.

APA, Harvard, Vancouver, ISO, and other styles

18

Inoue, Kohei, and Kiichi Urahama. "Non-photorealistic Halftoning with Additively Weighted Power Centroidal Voronoi Tessellation." Journal of The Institute of Image Information and Television Engineers 63, no. 9 (2009): 1258–60. http://dx.doi.org/10.3169/itej.63.1258.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Kitazono, Koichi, Shiyue Guo, Ke Zhu, Takuya Hamaguchi, and Yuta Fujimori. "Energy Absorption of Additively Manufactured Porous Metals with Disordered Cells." Materials Science Forum 1016 (January 2021): 183–87. http://dx.doi.org/10.4028/www.scientific.net/msf.1016.183.

Full text

Abstract:

Lightweight porous metals are focused on as energy absorbing materials for automobiles. Open-cell porous metals were manufactured through additive manufacturing process. Their cell structures were designed based on Voronoi diagrams using a commercial 3D-CAD software. Both ordered and disordered cell structures with the same porosities were successfully designed in this study. Compression tests and explicit finite element analysis revealed heterogeneous deformation behaviors in ordered porous metals. On the other hand, the porous metals with disordered cell structure showed relatively isotropic and uniform deformation, which is suitable as energy absorbing materials. Controlling the disordered cell structure designed by 3D-Voronoi diagram enables to develop the advanced porous metals having various mechanical properties.

APA, Harvard, Vancouver, ISO, and other styles

20

Hao, Zhanjun, Jianwu Dang, Yan Yan, and Xiaojuan Wang. "A node localization algorithm based on Voronoi diagram and support vector machine for wireless sensor networks." International Journal of Distributed Sensor Networks 17, no. 2 (February 2021): 155014772199341. http://dx.doi.org/10.1177/1550147721993410.

Full text

Abstract:

For wireless sensor network, the localization algorithm based on Voronoi diagram has been applied. However, the location accuracy node position in wireless sensor network needs to be optimized by the analysis of the literature, a node location algorithm based on Voronoi diagram and support vector machine is proposed in this article. The basic idea of the algorithm is to first divide the region into several parts using Voronoi diagram and anchor node in the localization region. The range of the initial position of the target node is obtained by locating the target node in each region and then the support vector machine is used to optimize the position of the target node accurately. The localization performance of the localization algorithm is analyzed by simulation and real-world experiments. The experimental results show that the localization algorithm proposed in this article is better than the optimal region selection strategy based on Voronoi diagram-based localization scheme and Weighted Voronoi diagram-based localization scheme localization algorithms in terms of localization accuracy. Therefore, the performance of the localization algorithm proposed in this article is verified.

APA, Harvard, Vancouver, ISO, and other styles

21

Lu, Xiaomin, Haowen Yan, Wende Li, Xiaojun Li, and Fang Wu. "An Algorithm based on the Weighted Network Voronoi Diagram for Point Cluster Simplification." ISPRS International Journal of Geo-Information 8, no. 3 (February 27, 2019): 105. http://dx.doi.org/10.3390/ijgi8030105.

Full text

Abstract:

Points on maps that stand for geographic objects such as settlements are generally connected by road networks. However, in the existing algorithms for point cluster simplification, points are usually viewed as discrete objects or their distances are considered in Euclidean spaces, and therefore the point cluster generalization results obtained by these algorithms are sometimes unreasonable. To take roads into consideration so that point clusters can be simplified in appropriate ways, the network Voronoi diagram is used and a new algorithm is proposed in this paper. First, the weighted network Voronoi diagram is constructed taking into account the weights of the points and the properties of the related road segments. Second, the network Voronoi polygons are generated and two factors (i.e., the area of the network Voronoi polygon and the total length of the dilated road segments in the polygon) are considered as the basis for point simplification. Last, a Cartesian coordinate system is built based on the two factors and the point clusters are simplified by means of the “concentric quadrants”. Our experiments show that the algorithm can effectively and correctly transmit types of information in the process of point cluster simplification, and the results are more reasonable than that generated by the ordinary Voronoi-based algorithm and the weighted Voronoi-based algorithm.

APA, Harvard, Vancouver, ISO, and other styles

22

Galvão, Lauro C., Antonio G. N. Novaes, J. E. Souza de Cursi, and João C. Souza. "A multiplicatively-weighted Voronoi diagram approach to logistics districting." Computers & Operations Research 33, no. 1 (January 2006): 93–114. http://dx.doi.org/10.1016/j.cor.2004.07.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Eder, Günther, and Martin Held. "Weighted Voronoi Diagrams in the Maximum Norm." International Journal of Computational Geometry & Applications 29, no. 03 (September 2019): 239–50. http://dx.doi.org/10.1142/s0218195919500079.

Full text

Abstract:

We consider multiplicatively weighted points, axis-aligned rectangular boxes and axis-aligned straight-line segments in the plane as input sites and study Voronoi diagrams of these sites in the maximum norm. For [Formula: see text] weighted input sites we establish a tight [Formula: see text] worst-case bound on the combinatorial complexity of their Voronoi diagram and introduce an incremental algorithm that allows its computation in [Formula: see text] time. Our approach also yields a truly simple [Formula: see text] algorithm for solving the one-dimensional version of this problem, where all weighted sites lie on a line.

APA, Harvard, Vancouver, ISO, and other styles

24

Yang, Xi, Fang Yan, and Jun Liu. "3D Localization Algorithm Based on Voronoi Diagram and Rank Sequence in Wireless Sensor Network." Scientific Programming 2017 (2017): 1–8. http://dx.doi.org/10.1155/2017/4769710.

Full text

Abstract:

Accurate nodes’ localization is a key problem in wireless sensor network (WSN for short). This paper discusses and analyzes the effects of Voronoi diagram in 3D location space. Then it proposes Sequence Localization Correction algorithm based on 3D Voronoi diagram (SLC3V), which introduces 3D Voronoi diagram to divide the 3D location space and constructs the rank sequence tables of virtual beacon nodes. SLC3V uses RSSI method between beacon nodes as a reference to correct the measured distance and fixes the location sequence of unknown nodes. Next, it selects optimal parameterNand realizes the weighted location estimate withNvalid virtual beacon nodes by normalization process of rank correlation coefficients. Compared with other sequence location algorithms, simulation experiments show that it can improve the localization accuracy for nodes in complex 3D space with less measurements and computational costs.

APA, Harvard, Vancouver, ISO, and other styles

25

Zhang, Pengyan, Wenlong Jing, and Yunzeng Chen. "Weighted Voronoi Diagram-Based Simulation and Comparative Analysis of Ecosystem Service Coverage: Case Study of the Zhongyuan Urban Agglomeration." Journal of Sensors 2018 (August 5, 2018): 1–11. http://dx.doi.org/10.1155/2018/7147524.

Full text

Abstract:

The future of ecology lies on the promotion of eco-economy, a resource saving and environment-friendly society, and the research of ecosystem services. This article applied weighted Voronoi diagram to simulate the ecosystem service capacity in Zhongyuan Urban Agglomeration, China, using remote sensing and geographic information systems. The results show that (1) compared with the traditional Voronoi diagram, the weighted Voronoi diagram expresses more accurate on the ecosystem service range, (2) the total value of the ecosystem service in the study area was 575.7 billion yuan in 2015.The maximum value was about 253.8 billion yuan greater than the minimum value. The unit forest ecosystem has been improved after the coefficient was modified, and the value of ecosystem services reached 32,638.87 yuan/hm2, (3) the service value of construction ecosystem has a great effect on the total value of ecosystem services; the overall pulldown effect of Kaifeng City is most considerable, and (4) the region with strong ecosystem service capacity has strong effect in annexing the nearby areas with weak ecosystem service capacity. And the distance of the annexing is inversely proportional. The closer the distance is, the stronger the annex will be.

APA, Harvard, Vancouver, ISO, and other styles

26

Lu, Xiaomin, and Haowen Yan. "An Algorithm to Generate a Weighted Network Voronoi Diagram Based on Improved PCNN." Applied Sciences 12, no. 12 (June 13, 2022): 6011. http://dx.doi.org/10.3390/app12126011.

Full text

Abstract:

The network Voronoi diagram has been extensively applied in many fields, such as influence area construction, location selection and urban planning, owing to its high accuracy and validity in space division. Taking advantage of parallel processing and auto-wave division of the pulse coupled neural network (PCNN), an algorithm for generating a weighted network Voronoi diagram is proposed in this paper. First, in order to better accommodate the scenes of urban facility points and road networks, the PCNN is improved. Second, the speed of the auto-wave in the improved PCNN is calculated by the weights of the facility points and the attributes of the related road network. Third, the nodes in the road network are considered as neurons, the facility points are projected onto the nearest road segments and the projected points are treated as initial neurons. The initial neurons generate auto-waves simultaneously, and the auto-waves transmit along the shortest path from neurons to other neurons with the calculated speed until all the neurons are fired. During this procedure, the road network and the corresponding space are assigned to the initial neurons and the weighted network Voronoi diagram is constructed. The experiments on the specific region with the real POIs present the feasibility, applicability and efficiency of the algorithm.

APA, Harvard, Vancouver, ISO, and other styles

27

LI, Rui, Jia-tian LI, Hua WANG, Hai-xia PU, and Yu-feng HE. "Algorithm for generating weighted Voronoi diagram based on quadtree structure." Journal of Computer Applications 32, no. 11 (May 26, 2013): 3078–81. http://dx.doi.org/10.3724/sp.j.1087.2012.03078.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Hurtado, Ferran, Rolf Klein, Elmar Langetepe, and Vera Sacristán. "The weighted farthest color Voronoi diagram on trees and graphs." Computational Geometry 27, no. 1 (January 2004): 13–26. http://dx.doi.org/10.1016/j.comgeo.2003.07.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Reitsma, René, and Stanislav Trubin. "Information Space Partitioning Using Adaptive Voronoi Diagrams." Information Visualization 6, no. 2 (January 2007): 123–38. http://dx.doi.org/10.1057/palgrave.ivs.9500152.

Full text

Abstract:

In this paper, we present and evaluate a Voronoi method for partitioning continuous information spaces. We define the formal characteristics of the problem and discuss several well-known partitioning methods and approaches. We submit that although they all partially solve the problem, they all have shortcomings. As an alternative, we offer an approach based on an adaptive version of the multiplicatively weighted Voronoi diagram. The diagram is ‘adaptive’ because it is computed backwards; that is, the generators' weights are treated as dependent rather than independent variables. We successfully test this adaptive solution using both ideal-typical (artificial) and empirical data. Since the resultant visualizations are meant to be used by human subjects, we then discuss the results of a usability experiment, positioning the adaptive solution against a commonly used rectangular solution and the classic nonweighted Voronoi solution. The results indicate that in terms of usability, both the rectangular and the adaptive Voronoi solution outperform the standard Voronoi solution. In addition, although subjects are better able to gage rectangular area relationships, only the adaptive Voronoi solution satisfies all geometric constraints of weight-proportional partitioning.

APA, Harvard, Vancouver, ISO, and other styles

30

Wang, Shiju, Zhiying Lu, Shaoyun Ge, and Chengshan Wang. "An Improved Substation Locating and Sizing Method Based on the Weighted Voronoi Diagram and the Transportation Model." Journal of Applied Mathematics 2014 (2014): 1–9. http://dx.doi.org/10.1155/2014/810607.

Full text

Abstract:

Substation locating and sizing is an important component of urban power networks. In this paper, an improved method based on the weighted Voronoi diagram and transportation model for substation planning is proposed, which can optimize the location, capacity, and power supply range for each substation with the minimum investment which contains the cost of the lines, substations, and annual operation expense. The weighted Voronoi diagram (WVD) whose weights can be adaptively adjusted can calculate the location and the capacity for each substation with good performance of global convergence and better convergence speed. Transportation model can simulate the best correspondence relationship between the loads and substations. The impact of geographical factors is also considered in this paper. Large amount of experiments show that the improved method can get more reasonable and more optimized planning result within shorter time than the original WVD and other algorithms.

APA, Harvard, Vancouver, ISO, and other styles

31

Isele-Holder, Rolf E., Brooks D. Rabideau, and Ahmed E. Ismail. "Definition and Computation of Intermolecular Contact in Liquids Using Additively Weighted Voronoi Tessellation." Journal of Physical Chemistry A 116, no. 18 (April 26, 2012): 4657–66. http://dx.doi.org/10.1021/jp3021886.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

MIAO, Lili, Weiguo JIANG, Yuan WAN, Shi HE, and Yunhao CHEN. "Beijing Urban Wetland Function Zoning Based on the Weighted Voronoi Diagram." Journal of Geo-information Science 15, no. 4 (2013): 554. http://dx.doi.org/10.3724/sp.j.1047.2013.00554.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Kobayashi, Kei, and Kokichi Sugihara. "Approximation of multiplicatively weighted crystal growth Voronoi diagram and its application." Electronics and Communications in Japan (Part III: Fundamental Electronic Science) 85, no. 6 (February 12, 2002): 21–31. http://dx.doi.org/10.1002/ecjc.1098.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Kim, Jeongeun, Chanyoung Ju, and Hyoung Il Son. "A Multiplicatively Weighted Voronoi-Based Workspace Partition for Heterogeneous Seeding Robots." Electronics 9, no. 11 (November 2, 2020): 1813. http://dx.doi.org/10.3390/electronics9111813.

Full text

Abstract:

Multi-robot systems (MRSs) are currently being used to perform agricultural tasks. In this regard, the deployment of heterogeneous MRSs will be essential for achieving more efficient and innovative farming in the future. In this paper, we propose a multiplicatively weighted (MW) Voronoi-based task-allocation scheme for heterogeneous agricultural robots. The seed points for area partitioning using a Voronoi diagram are obtained by performing node clustering using a k-means clustering algorithm. Heterogeneous robots have different specifications for performing various tasks. Thus, the proposed MW Voronoi-based area partitioning for heterogeneous robots is applied by considering various weighting factors. The path for each robot is computed such that the robot follows the nodes, and the computed paths serve as inputs for the workload distribution strategy that assigns paths to the robots. Simulations and field experiments were conducted to verify the effectiveness of the proposed approach.

APA, Harvard, Vancouver, ISO, and other styles

35

Du, Xiao Chuan, Xiu Cheng Guo, Xiao Hui Zhang, and Qiao Ying Ma. "Service Area Delimitation of Regional Highway Passenger Transport Hub Using Random-Utility-Based Weighted Voronoi Diagram." Applied Mechanics and Materials 253-255 (December 2012): 1765–70. http://dx.doi.org/10.4028/www.scientific.net/amm.253-255.1765.

Full text

Abstract:

This study introduces random utility theory to ordinary weighted Voronoi diagram and describes its application in delimiting the services area of a regional highway passenger transport hub. The Euclidean distance was replaced by a utility function of hub’s capacity factor, travel distance, travel time, and monetary travel cost from passenger’s initial origin to the alternative hubs. The service area was delimited based on utility maximization principle and a nested-logit model for transport hub and travel mode. The application shows that the service area of a hub is not consistent with its administrative boundary. It proves Voronoi diagram is a reasonable and practical tool for detecting the service boundary of a hub by offering an integrated angle to recognize the interacting relationship between hub location, transport network, and passenger’s choice behaviors.

APA, Harvard, Vancouver, ISO, and other styles

36

Yang, Xi, and Jun Liu. "Sequence Localization Algorithm Based on 3D Voronoi Diagram in Wireless Sensor Network." Applied Mechanics and Materials 644-650 (September 2014): 4422–26. http://dx.doi.org/10.4028/www.scientific.net/amm.644-650.4422.

Full text

Abstract:

For nodes’ self-localization in wireless sensor networks (WSN), a new localization algorithm called Sequence Localization algorithm based on 3D Voronoi diagram (SL3V) is proposed, which uses 3D Voronoi diagram to divide the localization space.It uses the polyhedron vertices as the virtual beacon nodes and constructs the rank sequence table of virtual beacon nodes. Then it computes Kendall coefficients of the ranks in the optimal rank sequence table and that of the unknown node. Finally, it realizes the weighted estimate of the unknown node by normalization processing Kendall coefficients. Simulation experiments prove that itcan obviously improve the localization accuracy compared with the traditional 2D sequence-based localization and can satisfy the need of localization for 3D space.

APA, Harvard, Vancouver, ISO, and other styles

37

BAE, SANG WON, and CHAN-SU SHIN. "THE ONION DIAGRAM: A VORONOI-LIKE TESSELLATION OF A PLANAR LINE SPACE AND ITS APPLICATIONS." International Journal of Computational Geometry & Applications 22, no. 01 (February 2012): 3–25. http://dx.doi.org/10.1142/s0218195912600011.

Full text

Abstract:

Given a set S of weighted points in the plane, we consider two problems dealing with lines in ℝ2 under the weighted Euclidean distance: (1) Preprocess S into a data structure that efficiently finds a nearest point among S to a query line. (2) Find an optimal line that maximizes the minimum of the weighted distance to any point of S. The latter problem is also known as the obnoxious line location problem. We introduce a unified approach to both problems based on a new geometric transformation that maps lines in the plane to points in a line space. It turns out that our transformation, together with its target space, well describes the proximity relations between given weighted points S and every line in ℝ2. We define a Voronoi-like tessellation on the line space and investigate its geometric, combinatorial, and computational properties. As its direct applications, we obtain several new algorithmic results on the two problems. We also show that our approach extends to weighted line segments and weighted polygons.

APA, Harvard, Vancouver, ISO, and other styles

38

Kim, Ki-Hwan, Eun-Hee Lee, and Song-You Hong. "Potential of Voronoi Diagram for the Conserved Remapping of Precipitation." Monthly Weather Review 146, no. 7 (July 1, 2018): 2237–46. http://dx.doi.org/10.1175/mwr-d-17-0350.1.

Full text

Abstract:

Abstract This study considers a remapping algorithm between irregularly distributed observations and grid points based on Voronoi diagrams and examines its potential for verification of precipitation forecasts. We propose a new remapping method using Voronoi diagrams to apply conservative area-weighted remapping on grid data to station points, describing a representative area for each station point. Conservative remapping is applied to interpolate daily precipitation data between grid and station points over South Korea. The proposed method shows significant differences from bilinear interpolation, which has been widely used in modeling communities, for local maximum and mean in a given domain. It is also shown that different interpolation methods have an impact on verification results of precipitation forecast from a numerical weather prediction model against station observations. It is suggested that the proposed method has potential to be used for verifying precipitation forecasts at in situ observation points, with its conservativeness and capability to be applied in any remapping direction between grids and stations.

APA, Harvard, Vancouver, ISO, and other styles

39

Telley, H., Th M. Liebling, A. Mocellin, and F. Righetti. "Simulating and Modelling Grain Growth as the Motion of a Weighted Voronoi Diagram." Materials Science Forum 94-96 (January 1992): 301–6. http://dx.doi.org/10.4028/www.scientific.net/msf.94-96.301.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Kiseliova, O. M., O. M. Prytomanova, and V. H. Padalko. "APPLICATION OF THE THEORY OF OPTIMAL SET PARTITIONING BEFORE BUILDING MULTIPLICATIVELY WEIGHTED VORONOI DIAGRAM WITH FUZZY PARAMETERS." EurasianUnionScientists 6, no. 2(71) (2020): 30–35. http://dx.doi.org/10.31618/esu.2413-9335.2020.6.71.615.

Full text

Abstract:

An algorithm for constructing a multiplicatively weighted Voronoi diagram involving fuzzy parameters with the optimal location of a finite number of generator points in a limited set of n-dimensional Euclidean space 𝐸𝑛 has been suggested in the paper. The algorithm has been developed based on the synthesis of methods of solving the problems of optimal set partitioning theory involving neurofuzzy technologies modifications of N.Z. Shor 𝑟 -algorithm for solving nonsmooth optimization problems.

APA, Harvard, Vancouver, ISO, and other styles

41

Yan, Haowen, and Jonathan Li. "An approach to simplifying point features on maps using the multiplicative weighted Voronoi diagram." Journal of Spatial Science 58, no. 2 (September 2013): 291–304. http://dx.doi.org/10.1080/14498596.2013.815578.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Liu, Jingna, Xiaoyun Sun, and Shujuan Liu. "Weighted Node Network Voronoi Diagram and its application to optimization of chain stores layout." International Journal of Machine Learning and Cybernetics 7, no. 4 (January 27, 2016): 679–88. http://dx.doi.org/10.1007/s13042-015-0491-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Lu, Zhiying, Shaoyun Ge, Chengshan Wang, and Shiju Wang. "Substation planning method based on the weighted Voronoi diagram using an intelligent optimisation algorithm." IET Generation, Transmission & Distribution 8, no. 12 (December 1, 2014): 2173–82. http://dx.doi.org/10.1049/iet-gtd.2013.0614.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Zhang, W., J. Li, Y. Wang, Y. Xiao, P. Liu, and S. Zhang. "A LANDMARK EXTRACTION METHOD ASSOCIATED WITH GEOMETRIC FEATURES AND LOCATION DISTRIBUTION." ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences XLII-3 (April 30, 2018): 2307–13. http://dx.doi.org/10.5194/isprs-archives-xlii-3-2307-2018.

Full text

Abstract:

Landmark plays an important role in spatial cognition and spatial knowledge organization. Significance measuring model is the main method of landmark extraction. It is difficult to take account of the spatial distribution pattern of landmarks because that the significance of landmark is built in one-dimensional space. In this paper, we start with the geometric features of the ground object, an extraction method based on the target height, target gap and field of view is proposed. According to the influence region of Voronoi Diagram, the description of target gap is established to the geometric representation of the distribution of adjacent targets. Then, segmentation process of the visual domain of Voronoi K order adjacent is given to set up target view under the multi view; finally, through three kinds of weighted geometric features, the landmarks are identified. Comparative experiments show that this method has a certain coincidence degree with the results of traditional significance measuring model, which verifies the effectiveness and reliability of the method and reduces the complexity of landmark extraction process without losing the reference value of landmark.

APA, Harvard, Vancouver, ISO, and other styles

45

Wu, Xiao Yong, and Wei Jun Zhong. "Research on Capability Deployment of ASW Systems." Advanced Materials Research 722 (July 2013): 566–71. http://dx.doi.org/10.4028/www.scientific.net/amr.722.566.

Full text

Abstract:

In anti-submarine war systems of system (ASW-SOS), each operational node has a variety of combat capabilities, which play different roles in anti-submarine actions, and these abilities have their own range. Therefore, after definition and description of ability of operational node, calculation of comprehensive ability index, and built of weighted voronoi diagram (WVD), the analysis approach of operational ability of ASW-SOS is formed. After generating various capabilities WVD, this paper analyzes impact of change brought by global dynamic deployment, and puts forward adaptive optimization solution. The simulation results show that, by using the technology of WVD, the ability of static distribution and dynamic change process can be demonstrated clearly and precisely, and this method has strong practicality

APA, Harvard, Vancouver, ISO, and other styles

46

TAN, Li, Xiaojiang TANG, Anbar HUSSAIN, and Haoyu WANG. "A Weighted Voronoi Diagram-Based Self-Deployment Algorithm for Heterogeneous Directional Mobile Sensor Networks in Three-Dimensional Space." IEICE Transactions on Communications E103.B, no. 5 (May 1, 2020): 545–58. http://dx.doi.org/10.1587/transcom.2019ebp3111.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Gao, Jiabin, Wenze Yue, Xinyue Ye, and Dong Li. "Identification of Potential Over-Supply Zones of Urban Shopping Malls: Integration of Crowdsourced Data and Weighted Voronoi Diagram." Journal of Urban Technology 26, no. 3 (April 26, 2019): 65–79. http://dx.doi.org/10.1080/10630732.2019.1595991.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Marx, Dániel, and Michał Pilipczuk. "Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams." ACM Transactions on Algorithms 18, no. 2 (April 30, 2022): 1–64. http://dx.doi.org/10.1145/3483425.

Full text

Abstract:

We study a general family of facility location problems defined on planar graphs and on the two-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the n O (√ k ) time brute force algorithm of selecting k objects can be improved to n O (√ k ) time. The algorithm is based on an idea that was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. We focus on the Voronoi diagram of a hypothetical solution of k objects, guess a balanced separator cycle of this Voronoi diagram to obtain a set that separates the solution in a balanced way, and then recurse on the resulting subproblems. The following list is an exemplary selection of concrete consequences of our main result. We can solve each of the following problems in time n O (√ k ), where n is the total size of the input: d -Scattered Set : find k vertices in an edge-weighted planar graph that pairwise are at distance at least d from each other ( d is part of the input). d -Dominating Set (or ( k,d )-Center): find k vertices in an edge-weighted planar graph such that every vertex of the graph is at distance at most d from at least one selected vertex ( d is part of the input). Given a set D of connected vertex sets in a planar graph G , find k disjoint vertex sets in D . Given a set D of disks in the plane (of possibly different radii), find k disjoint disks in D . Given a set D of simple polygons in the plane, find k disjoint polygons in D . Given a set D of disks in the plane (of possibly different radii) and a set P of points, find k disks in D that together cover the maximum number of points in P . Given a set D of axis-parallel squares in the plane (of possibly different sizes) and a set P of points, find k squares in D that together cover the maximum number of points in P . It is known from previous work that, assuming the Exponential Time Hypothesis (ETH), there is no f ( k ) n o (√ k ) time algorithm for any computable function f for any of these problems. Furthermore, we give evidence that packing problems have n O (√ k ) time algorithms for a much more general class of objects than covering problems have. For example, we show that, assuming ETH, the problem where a set D of axis-parallel rectangles and a set P of points are given, and the task is to select k rectangles that together cover the entire point set, does not admit an f ( k ) n o ( k ) time algorithm for any computable function f .

APA, Harvard, Vancouver, ISO, and other styles

49

Somayehee, Farshad, Amir Ali Nikkhah, and Jafar Roshanian. "Uniform Star Catalogue using GWKM Clustering for Application in Star Sensors." Journal of Navigation 72, no. 04 (January 21, 2019): 948–64. http://dx.doi.org/10.1017/s0373463318001029.

Full text

Abstract:

In this paper, a novel algorithm of weighted k-means clustering with geodesic criteria is presented to generate a uniform database for a star sensor. For this purpose, selecting the appropriate star catalogue and desirable minimum magnitude and eliminating double stars are among the steps of the uniformity process. Further, Delaunay triangulation and determining the scattered data density by using a Voronoi diagram were used to solve the problems of the proposed clustering method. Thus, by running a Monte Carlo simulation to count the number of stars observed in different fields of view, it was found that the uniformity leads to a significant reduction of the probability of observing a large number of stars in all fields of view. In contrast, the uniformity slightly increased the field of view needed to observe the minimum number of required stars for an identification algorithm.

APA, Harvard, Vancouver, ISO, and other styles

50

Andrews, Keith, Wolfgang Kienreich, Vedran Sabol, Jutta Becker, Georg Droschl, Frank Kappe, Michael Granitzer, Peter Auer, and Klaus Tochtermann. "The InfoSky visual explorer: Exploiting Hierarchical Structure and Document Similarities." Information Visualization 1, no. 3-4 (December 2002): 166–81. http://dx.doi.org/10.1057/palgrave.ivs.9500023.

Full text

Abstract:

InfoSky is a system enabling users to explore large, hierarchically structured document collections. Similar to a real-world telescope, InfoSky employs a planar graphical representation with variable magnification. Documents of similar content are placed close to each other and are visualised as stars, forming clusters with distinct shapes. For greater performance, the hierarchical structure is exploited and force-directed placement is applied recursively at each level on much fewer objects, rather than on the whole corpus. Collections of documents at a particular level in the hierarchy are visualised with bounding polygons using a modified weighted Voronoi diagram. Their area is related to the number of documents contained. Textual labels are displayed dynamically during navigation, adjusting to the visualisation content. Navigation is animated and provides a seamless zooming transition between summary and detail view. Users can map metadata such as document size or age to attributes of the visualisation such as colour and luminance. Queries can be made and matching documents or collections are highlighted. Formative usability testing is ongoing; a small baseline experiment comparing the telescope browser to a tree browser is discussed.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Additively Weighted Voronoi Diagram'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles