This paper concerns the behavior of an SINR diagram of wireless systems, composed of a set S of n stations embedded in Rd, when restricted to the corresponding Voronoi diagram imposed on S. The ...diagram obtained by restricting the SINR zones to their corresponding Voronoi cells is referred to hereafter as an SINR+Voronoi diagram.
Uniform SINR diagrams, where all stations transmit with the same power, are simple and nicely structured, e.g., the station reception zones are convex and “fat”. In contrast, nonuniform SINR diagrams might be complex; the reception zones might be fractured and their boundaries might contain many singular points. In this paper, we establish the perhaps surprising fact that a nonuniform SINR+Voronoi diagram is topologically almost as nice as a uniform SINR diagram. In particular, it is convex and effectively5 fat. This holds for every power assignment, every path-loss parameter α and every dimension d≥1. The convexity property also holds for every SINR threshold β>0, and the effective fatness property holds for any β>1. These fundamental properties provide a theoretical justification to engineering practices basing zonal tessellations on the Voronoi diagram, and help to explain the soundness and efficacy of such practices.
We also consider two algorithmic applications. The first concerns the Power Control with Voronoi Diagram (PCVD) problem, where given n stations embedded in some polygon P, it is required to find the power assignment that optimizes the SINR threshold of the transmission station si for any given reception point p∈P in its Voronoi cell ▪. The second application is approximate point location; we show that for SINR+Voronoi zones, this task can be solved considerably more efficiently than in the general non-uniform case.
Influence-based Voronoi diagrams of clusters Huang, Ziyun; Chen, Danny Z.; Xu, Jinhui
Computational geometry : theory and applications,
June 2021, 2021-06-00, Letnik:
96
Journal Article
Recenzirano
Odprti dostop
In this paper, we study a generalization of Voronoi diagram, called the Influence-based Voronoi Diagram (IVD). The input consists of a point set P in Rd, a collection C={C1,C2,…,Cn} where each Ci⊆P, ...i=1,2,…,n, is a cluster of points of P, and an influence function F(C,q) measuring the influence from a set C of points to any point q in Rd, and the goal is to construct an influence-based Voronoi diagram for C. By making use of a recent work called the Clustering Induced Voronoi Diagram (CIVD) for unclustered points, we are able to show that it is possible to utilize CIVD's space-partition ability and combine it with a divide-and-conquer algorithm to simultaneously resolve the space partition and assignment problems for a large class of influence functions. This overcomes a major difficulty of CIVD on the assignment problem. Our technique yields a (1−ϵ)-approximate IVD with size O(NlogN) in O(T2(N)Nlog2N+T1(N)) time, where N is the total cardinalities of clusters in C, ϵ>0 is a small constant, and T1 and T2 are functions measuring how efficiently F(C,q) can be evaluated.
We consider a Voronoi-like partition problem in the plane for a given finite set of generators. Each element in this partition is uniquely associated with a particular generator in the following ...sense: an agent that resides within a set of the partition at a given time will arrive at the generator associated with this set faster than any other agent that resides anywhere outside this set at the same instant of time. The agent’s motion is affected by the presence of a temporally varying drift, which is induced by local winds/currents. As a result, the minimum time to a destination is not equivalent to the minimum distance traveled. This simple fact has important ramifications over the partitioning problem. It is shown that this problem can be interpreted as a Dynamic Voronoi Diagram problem, where the generators are not fixed, but rather they are moving targets to be reached in minimum time. The problem is solved by first reducing it to a standard Voronoi Diagram by means of a time-varying coordinate transformation. We then extend the approach to solve the dual problem where the generators are the initial locations of a given set of agents distributed over the plane, such that each element in the partition consists of the terminal positions that can be reached by the corresponding agent faster than any other agent.
3D printing, also called additive manufacturing, has been increasingly popular and printing efficiency has become more critical. To print artifacts faster with less material, thus leading to lighter ...and cheaper printed products, various types of void structureshave been designed and engineered inside of shape models. In this paper, we present a novel method for generating support-free elliptic hollowing for 3D shapes which can entirely avoid additional supporting structures. To achieve this, we perform the ellipse hollowing in one of the cross sectional polygons and then extrude the hollowed ellipses to the other parallel cross sections. To efficiently pack the ellipses in the polygon, we construct the Voronoi diagram of ellipses to reason the free-space around the ellipses and other geometric features by taking advantage of the available algorithm for the efficient and robust construction of the Voronoi diagram of circles. We demonstrate the effectiveness and feasibility of our proposed method by designing and printing support-free hollow for various 3D shapes using Poretron, the program which computes the hollow by embedding appropriate APIs of the Voronoi Diagram Machine library that is freely available from Voronoi Diagram Research Center. It takes a 3D mesh model and produces an STL file which can be either fed into a 3D printer or postprocessed.
Display omitted
•Support-free elliptic hollowing for 3D shapes via ellipse packing.•Derivation of a class of support-free ellipses.•Packing the support-free ellipses within a polygon (a cross-section of a 3D shape).•Packing the ellipses within a polygon is solved very efficiently and precisely via Voronoi diagram.
We build a rigorous bridge between deep networks (DNs) and approximation theory via spline functions and operators. Our key result is that a large class of DNs can be written as a composition of ...max-affine spline operators (MASOs) that provide a powerful portal through which we view and analyze their inner workings. For instance, conditioned on the spline partition region containing the input signal, the output of an MASO DN can be written as a simple affine transformation of the input. This implies that a DN constructs a set of signal-dependent, class-specific templates against which the signal is compared via a simple inner product; we explore the links to the classical theory of optimal classification via matched filters and the effects of data memorization. Going further, we propose a simple penalty term that can be added to the cost function of any DN learning algorithm to force the templates to be orthogonal with each other; this leads to significantly improved classification performance and reduced overfitting with no change to the DN architecture. The spline partition of the input signal space that is implicitly induced by an MASO directly links DNs to the theory of vector quantization (VQ) and K-means clustering, which opens up new geometric avenues to study how DNs organize signals in a hierarchical fashion. To validate the utility of the VQ interpretation, we develop and validate a new distance metric for signals and images that quantify the difference between their VQ encodings.
In this paper, we propose to compute Voronoi diagrams over mesh surfaces driven by an arbitrary geodesic distance solver, assuming that the input is a triangle mesh as well as a collection of sites P ...= {Pi}mi=1 on the surface. We propose two key techniques to solve this problem. First, as the partition is determined by minimizing the m distance fields, each of which rooted at a source site, we suggest keeping one or more distance triples, for each triangle, that may help determine the Voronoi bisectors when one uses a mark-and-sweep geodesic algorithm to predict the multi-source distance field. Second, rather than keep the distance itself at a mesh vertex, we use the squared distance to characterize the linear change of distance field restricted in a triangle, which is proved to induce an exact VD when the base surface reduces to a planar triangle mesh. Specially, our algorithm also supports the Euclidean distance, which can handle thin-sheet models (e.g. leaf) and runs faster than the traditional restricted Voronoi diagram (RVD) algorithm. It is very extensible to deal with various variants of surface-based Voronoi diagrams including (1) surface-based power diagram, (2) constrained Voronoi diagram with curve-type breaklines, and (3) curve-type generators. We conduct extensive experimental results to validate the ability to approximate the exact VD in different distance-driven scenarios.
In a typical Internet of Things (IoT) deployment such as smart cities and Industry 4.0, the amount of sensory data collected from physical world is significant and wide-ranging. Processing large ...amount of real-time data from the diverse IoT devices is challenging. For example, in IoT environment, wireless sensor networks (WSN) are typically used for the monitoring and collecting of data in some geographic area. Spatial range queries with location constraints to facilitate data indexing are traditionally employed in such applications, which allows the querying and managing the data based on SQL structure. One particular challenge is to minimize communication cost and storage requirements in multi-dimensional data indexing approaches. In this paper, we present an energy- and time-efficient multidimensional data indexing scheme, which is designed to answer range query. Specifically, we propose data indexing methods which utilize hierarchical indexing structures, using binary space partitioning (BSP), such as kd-tree, quad-tree, k-means clustering, and Voronoi-based methods to provide more efficient routing with less latency. Simulation results demonstrate that the Voronoi Diagram-based algorithm minimizes the average energy consumption and query response time.
•We present a high-dimensional data indexing scheme based on Voronoi Diagrams for spatial query processing in IoT.•The scheme aggregates multi-attribute sensor data in an energy- and time-efficient manner.•Hierarchical in-network storage is used to provide fast query responses.•Performance evaluation demonstrates effectiveness of our scheme compared to other data structures.
A new parametric method for the design of Voronoi-based lattice porous structures is proposed in this paper. First, the functional relationship between the porosity p, the number of seed points n, ...and the beam radius r is established. The design space is then divided into individual unit cells, and the seed points and beam radius values of each unit cell are calculated. In each unit cell, Voronoi tessellation is used to generate uniformly distributed seed points. Finally in the design space, all seed points are Voronoi tessellated globally, and the edges are cylindered with corresponding beam radius values. With this design method, not only can the lattice structures with uniform or graded distribution of porosity be generated, but the customized lattice structures can also be generated according to the porosity of each unit cell. Through the analysis of model data, it is verified that the uniform distribution of seed points in this paper is stable and the porosity of the model is consistent with the design value. The distribution of pore spheres between pores is used to illustrate that the lattice porous structures designed in this paper is globally controllable and locally uniform.
Display omitted
•A design approach is proposed to determine the structural parameters from the characterization parameters.•The function relationship between porosity and the number of seed points and beam radius is established.•Combine the design features of lattice and open-cell foam.•A globally controllable and locally uniform graded lattice structure is designed.•The size and distribution of the pore spheres are used to evaluate the pore characteristics.
Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem in a long time; similarly, for any concrete Voronoi diagram of generalized (non-point) sites. ...In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion of one site. To achieve this result, we use the concept of a Voronoi-like diagram, a relaxed Voronoi structure of independent interest. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept and prove that it is robust under insertion, therefore, enabling its use in incremental constructions. The time-complexity analysis introduces a variant to backwards analysis, which is applicable to order-dependent structures. We further extend the technique to compute in expected linear time: the order-
(
k
+
1
)
subdivision within an order-
k
Voronoi region, and the farthest abstract Voronoi diagram, after the order of its regions at infinity is known.
PDF
