Theta graphs are important geometric graphs that have many applications, including wireless networking, motion planning, real-time animation, and minimum-spanning tree construction. We give closed form expressions for the average degree of theta graphs of a homogeneous Poisson point process over the plane. We then show that essentially the same bounds---with vanishing error terms---hold for theta graphs of finite sets of points that are uniformly distributed in a square. Finally, we show that the number of edges in a theta graph of points uniformly distributed in a square is concentrated around its expected value.
Bern al @cite_0 study the maximum degree of Delaunay triangulations of random point sets. Devroye al study the maximum degree of Gabriel graphs @cite_17 of random point sets. Arkin al @cite_14 study the length of the longest edge in Delaunay triangulations of random point sets.
@cite_0 @cite_14 @cite_17
2144793572 2952961426 2033513442
This paper presents a kinetic data structure (KDS) for maintenance of the Euclidean minimum spanning tree (EMST) on a set of moving points in 2-dimensional space. For a set of n points moving in the plane we build a KDS of size O(n) in O(nlogn) preprocessing time by which the EMST is maintained efficiently during the motion. This is done by applying the required changes to the combinatorial structure of the EMST which is changed in discrete timestamps. We assume that the motion of the points, i.e. x and y coordinates of the points, are defined by algebraic functions of constant maximum degree. In terms of the KDS performance parameters, our KDS is responsive, local, and compact. The presented KDS is based on monitoring changes of the Delaunay triangulation of the points and edge-length changes of the edges of the current Delaunay triangulation. Several localized routing protocols (see Bose, P. and Morin, P., Proc. 10th Annual Int. Symp. on Algorithms and Computation ISAAC, 1999) guarantee the delivery of packets when the underlying network topology is the Delaunay triangulation of all wireless nodes. However, it is expensive to construct the Delaunay triangulation in a distributed manner. Given a set of wireless nodes, we more accurately model the network as a unit-disk graph, UDG, in which a link between two nodes exists only if the distance between them is at most the maximum transmission range. Given a graph H, a spanning subgraph G of H is a t-spanner if the length of the shortest path connecting any two points in G is no more than t times the length of the shortest path connecting the two points in H. We present a novel localized networking protocol that constructs a planar 2.5-spanner of UDG, called the localized Delaunay triangulation, as network topology. It contains all edges that are in both the UDG and the Delaunay triangulation of all wireless nodes. Our experiments show that the delivery rates of existing localized routing protocols are increased when localized Delaunay triangulation is used instead of several previously proposed topologies. The total communication cost of our networking protocol is O(n log n) bits. Moreover, the computation cost of each node u is O(d sub u log d sub u ), where d sub u is the number of 1-hop neighbors of u in UDG. We give an expected-case analysis of Delaunay triangulations. To avoid edge effects we consider a unit-intensity Poisson process in Euclidean d-space, and then limit attention to the portion of the triangulation within a cube of side n1 d. For d equal to two, we calculate the expected maximum edge length, the expected minimum and maximum angles, and the average aspect ratio of a triangle. We also show that in any fixed dimension the expected maximum vertex degree is Θ(log n loglog n). Altogether our results provide some measure of the suitability of the Delaunay triangulation for certain applications, such as interpolation and mesh generation. An assumption of nearly all algorithms in computational geometry is that the input points are given precisely, so it is interesting to ask what is the value of imprecise information about points. We show how to preprocess a set of n disjoint unit disks in the plane in O(nlogn) time so that if one point per disk is specified with precise coordinates, the Delaunay triangulation can be computed in linear time. From the Delaunay, one can obtain the Gabriel graph and a Euclidean minimum spanning tree; it is interesting to note the roles that these two structures play in our algorithm to quickly compute the Delaunay.