Skip to main content
Top

2011 | Book

Transactions on Computational Science XIV

Special Issue on Voronoi Diagrams and Delaunay Triangulation

Editors: Marina L. Gavrilova, C. J. Kenneth Tan, Mir Abolfazl Mostafavi

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

insite
SEARCH

About this book

The 14th issue of the Transactions on Computational Science journal contains nine papers, all revised and extended versions of papers presented at the International Symposium on Voronoi Diagrams 2010, held in Quebec City, Canada, in June 2010. The topics covered include: the development of new generalized Voronoi diagrams and algorithms including round-trip Voronoi diagrams, maximal zone diagrams, Jensen-Bregman Voronoi diagrams, hyperbolic Voronoi diagrams, and moving network Voronoi diagrams; new algorithms based on Voronoi diagrams for applications in science and engineering, including geosensor networks deployment and optimization and homotopic object reconstruction; and the application of Delaunay triangulation for modeling and representation of Cosmic Web and rain fall distribution.

Table of Contents

Frontmatter
Revisiting Hyperbolic Voronoi Diagrams in Two and Higher Dimensions from Theoretical, Applied and Generalized Viewpoints
Abstract
This paper revisits hyperbolic Voronoi diagrams, which have been investigated since mid 1990’s by Onishi et al., from three standpoints, background theory, new applications, and geometric extensions.
First, we review two ideas to compute hyperbolic Voronoi diagrams of points. One of them is Onishi’s method to compute a hyperbolic Voronoi diagram from a Euclidean Voronoi diagram. The other one is a linearization of hyperbolic Voronoi diagrams. We show that a hyperbolic Voronoi diagram of points in the upper half-space model becomes an affine diagram, which is part of a power diagram in the Euclidean space. This gives another proof of a result obtained by Nielsen and Nock on the hyperbolic Klein model. Furthermore, we consider this linearization from the view point of information geometry. In the parametric space of normal distributions, the hyperbolic Voronoi diagram is induced by the Fisher metric while the divergence diagram is given by the Kullback-Leibler divergence on a dually flat structure. We show that the linearization of hyperbolic Voronoi diagrams is similar to one of two flat coordinates in the dually flat space, and our result is interesting in view of the linearization having information-geometric interpretations.
Secondly, from the viewpoint of new applications, we discuss the relation between the hyperbolic Voronoi diagram and the greedy embedding in the hyperbolic plane. Kleinberg proved that in the hyperbolic plane the greedy routing is always possible. We point out that results of previous studies about the greedy embedding use a property that any tree is realized as a hyperbolic Delaunay graph easily.
Finally, we generalize hyperbolic Voronoi diagrams. We consider hyperbolic Voronoi diagrams of spheres by two measures and hyperbolic Voronoi diagrams of geodesic segments, and propose algorithms for them, whose ideas are similar to those of computing hyperbolic Voronoi diagrams of points.
Toshihiro Tanuma, Hiroshi Imai, Sonoko Moriyama
Mollified Zone Diagrams and Their Computation
Abstract
The notion of the zone diagram of a finite set of points in the Euclidean plane is an interesting and rich variation of the classical Voronoi diagram, introduced by Asano, Matoušek, and Tokuyama [1]. In this paper, we define mollified versions of zone diagram named territory diagram and maximal territory diagram. A zone diagram is a particular maximal territory diagram satisfying a sharp dominance property. The proof of existence of maximal territory diagrams depends on less restrictive initial conditions and is established via Zorn’s lemma in contrast to the use of fixed-point theory in proving the existence of the zone diagram. Our proof of existence relies on a characterization which allows embedding any territory diagram into a maximal one. Our analysis of the structure of maximal territory diagrams is based on the introduction of a pair of dual concepts we call safe zone and forbidden zone. These in turn give rise to computational algorithms for the approximation of maximal territory diagrams. Maximal territory diagrams offer their own interesting theoretical and computational challenges, as well as insights into the structure of zone diagrams. This paper extends and updates previous work presented in [4].
Sergio C. de Biasi, Bahman Kalantari, Iraj Kalantari
Alpha, Betti and the Megaparsec Universe: On the Topology of the Cosmic Web
Abstract
We study the topology of the Megaparsec Cosmic Web in terms of the scale-dependent Betti numbers, which formalize the topological information content of the cosmic mass distribution. While the Betti numbers do not fully quantify topology, they extend the information beyond conventional cosmological studies of topology in terms of genus and Euler characteristic. The richer information content of Betti numbers goes along the availability of fast algorithms to compute them.
For continuous density fields, we determine the scale-dependence of Betti numbers by invoking the cosmologically familiar filtration of sublevel or superlevel sets defined by density thresholds. For the discrete galaxy distribution, however, the analysis is based on the alpha shapes of the particles. These simplicial complexes constitute an ordered sequence of nested subsets of the Delaunay tessellation, a filtration defined by the scale parameter, α. As they are homotopy equivalent to the sublevel sets of the distance field, they are an excellent tool for assessing the topological structure of a discrete point distribution. In order to develop an intuitive understanding for the behavior of Betti numbers as a function of α, and their relation to the morphological patterns in the Cosmic Web, we first study them within the context of simple heuristic Voronoi clustering models. These can be tuned to consist of specific morphological elements of the Cosmic Web, i.e. clusters, filaments, or sheets. To elucidate the relative prominence of the various Betti numbers in different stages of morphological evolution, we introduce the concept of alpha tracks.
Subsequently, we address the topology of structures emerging in the standard LCDM scenario and in cosmological scenarios with alternative dark energy content. The evolution of the Betti numbers is shown to reflect the hierarchical evolution of the Cosmic Web. We also demonstrate that the scale-dependence of the Betti numbers yields a promising measure of cosmological parameters, with a potential to help in determining the nature of dark energy and to probe primordial non-Gaussianities. We also discuss the expected Betti numbers as a function of the density threshold for superlevel sets of a Gaussian random field.
Finally, we introduce the concept of persistent homology. It measures scale levels of the mass distribution and allows us to separate small from large scale features. Within the context of the hierarchical cosmic structure formation, persistence provides a natural formalism for a multiscale topology study of the Cosmic Web.
Rien van de Weygaert, Gert Vegter, Herbert Edelsbrunner, Bernard J. T. Jones, Pratyush Pranav, Changbom Park, Wojciech A. Hellwing, Bob Eldering, Nico Kruithof, E. G. P. (Patrick) Bos, Johan Hidding, Job Feldbrugge, Eline ten Have, Matti van Engelen, Manuel Caroli, Monique Teillaud
Skew Jensen-Bregman Voronoi Diagrams
Abstract
A Jensen-Bregman divergence is a distortion measure defined by a Jensen convexity gap induced by a strictly convex functional generator. Jensen-Bregman divergences unify the squared Euclidean and Mahalanobis distances with the celebrated information-theoretic Jensen-Shannon divergence, and can further be skewed to include Bregman divergences in limit cases. We study the geometric properties and combinatorial complexities of both the Voronoi diagrams and the centroidal Voronoi diagrams induced by such as class of divergences. We show that Jensen-Bregman divergences occur in two contexts: (1) when symmetrizing Bregman divergences, and (2) when computing the Bhattacharyya distances of statistical distributions. Since the Bhattacharyya distance of popular parametric exponential family distributions in statistics can be computed equivalently as Jensen-Bregman divergences, these skew Jensen-Bregman Voronoi diagrams allow one to define a novel family of statistical Voronoi diagrams.
Frank Nielsen, Richard Nock
Continuous-Time Moving Network Voronoi Diagram
Abstract
We study the problem of moving network Voronoi diagram: given a network with n nodes and E edges. Suppose there are m sites (cars, postmen, etc) moving along the network edges, we design the algorithms to compute the dynamic network Voronoi diagram as sites move such that we can answer the nearest neighbor query efficiently. Furthermore, we extend it to the k-order dynamic network Voronoi diagram such that we can answer the k nearest neighbor query efficiently. We also study the problem when the query point is allowed to move at a given speed. Moreover, we give the algorithm for the half-online version of moving network Voronoi diagram.
Chenglin Fan, Jun Luo, Binhai Zhu
A GIS Based Wireless Sensor Network Coverage Estimation and Optimization: A Voronoi Approach
Abstract
Recent advances in sensor technology have resulted in the design and development of more efficient and low cast sensor networks for environmental monitoring, object surveillance, tracking and controlling of moving objects, etc. The deployment of a sensor network in a real environment presents several challenging issues that are often oversimplified in the existing solutions. Different approaches have been proposed in the literatures to solve this problem. Many of these approaches use Voronoi diagram and Delaunay triangulation to identify sensing holes in the network and create an optimal arrangement of the sensors to eliminate the holes. However, most of these methods do not consider the reality of the environment in which the sensor network is deployed. This paper presents a survey of the existing solutions for geosensor network optimization that use Voronoi diagram and Delaunay triangulation and identifies their limitations in a real world application. Next, it proposes a more realistic approach by integrating spatial information in the optimization process based on Voronoi diagram. Finally the results of two cases studies based on the proposed approach in natural area and urban environment are presented and discussed.
Meysam Argany, Mir Abolfazl Mostafavi, Farid Karimipour, Christian Gagné
Rainfall Distribution Based on a Delaunay Triangulation Method
Abstract
Many rainfall-run-off distributed models need rainfall data as input on a pixel by pixel basis, for each time interval. Due to the large amount of pixels that can make up a basin (proportional to the map scale), a fast and efficient method must be devised in order to obtain the rainfall field for each time interval (e.g. 20 minutes). Most models use interpolation methods such as the Inverse Distance Weighted. However, we propose the use of a Delaunay Triangulation using the incremental algorithm developed by Watson where the rainfall stations are used as the vertices of the triangles that represent a three dimensional plane of the rainfall. Once the equation of the plane is known, a rainfall value for each pixel is calculated. We compare both methods and evaluate the sensitivity to changes in time and spatial scales separately.
Nicolas Velasquez, Veronica Botero, Jaime Ignacio Velez
Homotopic Object Reconstruction Using Natural Neighbor Barycentric Coordinates
Abstract
One of the challenging problems in computer vision is object reconstruction from cross sections. In this paper, we address the problem of 2D object reconstruction from arbitrary linear cross sections. This problem has not been much discussed in the literature, but holds great importance since it lifts the requirement of order within the cross sections in a reconstruction problem, consequently making the reconstruction problem harder. Our approach to the reconstruction is via continuous deformations of line intersections in the plane. We define Voronoi diagram based barycentric coordinates on the edges of n-sided convex polygons as the area stolen by any point inside a polygon from the Voronoi regions of each open oriented line segment bounding the polygon. These allow us to formulate homotopies on edges of the polygons from which the underlying object can be reconstructed. We provide results of the reconstruction including the necessary derivation of the gradient at polygon edges and the optimal placement of cutting lines. Accuracy of the suggested reconstruction is evaluated by means of various metrics and compared with one of the existing methods.
Ojaswa Sharma, François Anton
Round-Trip Voronoi Diagrams and Doubling Density in Geographic Networks
Abstract
Given a geographic network G (e.g. road network, utility distribution grid) and a set of sites (e.g. post offices, fire stations), a two-site Voronoi diagram labels each vertex v ∈ G with the pair of sites that minimizes some distance function. The sum function defines the “distance” from v to a pair of sites s,t as the sum of the distances from v to each site. The round-trip function defines the “distance” as the minimum length tour starting and ending at v and visiting both s and t. A two-color variant begins with two different types of sites and labels each vertex with the minimum pair of sites of different types. In this paper, we provide new properties and algorithms for two-site and two-color Voronoi diagrams for these distance functions in a geographic network, including experimental results on the doubling distance of various point-of-interest sites. We extend some of these results to multi-color variants.
Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, Ying Daisy Zhuo
Backmatter
Metadata
Title
Transactions on Computational Science XIV
Editors
Marina L. Gavrilova
C. J. Kenneth Tan
Mir Abolfazl Mostafavi
Copyright Year
2011
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-25249-5
Print ISBN
978-3-642-25248-8
DOI
https://doi.org/10.1007/978-3-642-25249-5