We provide a complete description of important geometric invariants of the Laplacian lattice of a multigraph under the distance function induced by a regular simplex, namely Voronoi Diagram, Delaunay Triangulation, Delaunay Polytope and its combinatorial structure, Shortest Vectors, Covering and Packing Radius. We use this information to obtain the following results: i. Every multigraph defines a Delaunay triangulation of its Laplacian lattice and this Delaunay triangulation contains complete information of the multigraph up to isomorphism. ii. The number of multigraphs with a given Laplacian lattice is controlled, in particular upper bounded, by the number of different Delaunay triangulations. iii. We obtain formulas for the covering and packing densities of a Laplacian lattice and deduce that in the space of Laplacian lattices of undirected connected multigraphs, the Laplacian lattices of highly connected multigraphs such as Ramanujan multigraphs possess good covering and packing properties.
ii. The Delaunay triangulation under the simplicial distance function provides more refined information on the underlying (connected) multigraph and in fact characterizes the multigraph completely up to isomorphism. On the other hand in the Euclidean case such an analogue is true only for three-connected graphs. A weaker result is known for general connected graphs @cite_0 .
@cite_0
2144793572 2161843738 2079037434 2052967435
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. 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. In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: given two points p and q of S and a real number L, compute (or approximate) a shortest path between p and q in the subgraph of the complete graph on S consisting of all edges whose lengths are less than or equal to L. We present efficient algorithms for answering several query problems of this type. Our solutions are based on Euclidean minimum spanning trees, spanners, and the Delaunay triangulation. A result of independent interest is the following. For any two points p and q of S, there is a path between p and q in the Delaunay triangulation, whose length is less than or equal to 2π (3 cos(π 6)) times the Euclidean distance |pq| between p and q, and all of whose edges have length at most |pq|. This work addresses the problem of approximating a manifold by a simplicial mesh, and the related problem of building triangulations for the purpose of piecewise-linear approximation of functions. It has long been understood that the vertices of such meshes or triangulations should be "well-distributed," or satisfy certain "sampling conditions." This work clarifies and extends some algorithms for finding such well-distributed vertices, by showing that they can be regarded as finding e-nets or Delone sets in appropriate metric spaces. In some cases where such Delone properties were already understood, such as for meshes to approximate smooth manifolds that bound convex bodies, the upper and lower bound results are extended to more general manifolds; in particular, under some general conditions, the minimum Hausdorff distance for a mesh with n simplices to a d-manifold M is Θ((∫M√|κ(x)| n)2 d) as n ⋺ ∞, where κ(x) is the Gaussian curvature at point x ∈ M. We also relate these constructions to Dudley's approximation scheme for convex bodies, which can be interpreted as involving an e-net in a metric space whose distance function depends on surface normals.