Generalized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence (Studies in Computational Intelligence, 158)

✍ Scribed by Marina L. Gavrilova (editor)

• Publisher: Springer
• Year: 2008
• Tongue: English
• Leaves: 312
• Edition: 2008
• Category: Library

✦ Synopsis

The year 2008 is a memorial year for Georgiy Vorono (1868-1908), with a number of events in the scientific community commemorating his tremendous contribution to the area of mathematics, especially number theory, through conferences and scientific gatherings in his honor. A notable event taking place in September 2008 a joint c- ference: the 5th Annual International Symposium on Voronoi Diagrams (ISVD) and the 4th International Conference on Analytic Number Theory and Spatial Tessel- tions held in Kyiv, Georgiy Vorono ’s native land. The main ideas expressed by G. Vorono ’s through his fundamental works have influenced and shaped the key dev- opments in computation geometry, image recognition, artificial intelligence, robotics, computational science, navigation and obstacle avoidance, geographical information systems, molecular modeling, astrology, physics, quantum computing, chemical en- neering, material sciences, terrain modeling, biometrics and other domains. This book is intended to provide the reader with in-depth overview and analysis of the fundamental methods and techniques developed following G. Voronoi ideas, in the context of the vast and increasingly growing area of computational intelligence. It represents the collection of state-of-the art research methods merging the bridges between two areas: geometric computing through Voronoi diagrams and intelligent computation techniques, pushing the limits of current knowledge in the area, impr- ing on previous solutions, merging sciences together, and inventing new ways of approaching difficult applied problems.

✦ Table of Contents

front-matter.pdf
fulltext.pdf
Computational Geometry Methods and Intelligent Computing
References
fulltext_2.pdf
Shapes of Delaunay Simplexes and Structural Analysis of Hard Sphere Packings
Introduction
Mathematical Background
Delaunay Simplexes
The Shape of the Delaunay Simplexes
Structural Types of Delaunay Simplexes
Structural Problems in Hard Sphere Packings
The Principle of Structural Organization of Non-crystalline Pickings
The Origin of the Bernal’s Limiting Density
Are There Other “Critical” Densities Besides 0.74, 0.64, and 0.55?
Statistically Preferable Configurations
Analysis of Hard Sphere Packings
Computer Models of Hard Spheres
Pair Correlation Function
Tetrahedra and Quartoctahedra
Crystallization in Hard Sphere Packings
Polytetrahedra
Conclusions about Structure of Hard Sphere Packings
Conclusion
References
fulltext_3.pdf
The $eta$-Shape and $eta$-Complex for Analysis of Molecular Structures
Introduction
$lpha$-Shape and Weighted $lpha$-Shape
$eta$-Hull and $eta$-Shape
$eta$-Hull
$eta$-Shape
The Voronoi Diagram of Atoms and a Quasi-triangulation
InterWorld Data Structure (IWDS) and Its Extension (eIWDS)
$eta$-Complex
Classification of Simplexes
Algorithms to Compute a $eta$-Complex and a $eta$-Shape
Applications in Molecular Biology
Molecular Surface
Extraction of Docking Sites
Mass Property
Conclusions
References
fulltext_4.pdf
Computational Geometry Analysis of Quantum State Space and Its Applications
Introduction
Preliminaries
Quantum States
Parameterization of Quantum States
Distances
Divergence
Quantum Channel and Its Capacity
Calculation of Holevo Capacity
Voronoi Diagrams for One-Qubit Quantum Statesand Its Application
Primal and Dual Voronoi Diagrams
Voronoi Diagrams for One-Qubit Pure States
Voronoi Diagrams for One-Qubit Mixed States
Voronoi Diagram for Three or Higher Level Quantum States
Euclidean Voronoi Diagram and Divergence Voronoi Diagram
Other Parameterization
Bures Distance and Fubini-Study Distance
Conclusion and Perspective
References
fulltext_5.pdf
Efficient Swarm Neighborhood Management Using the Layered Delaunay Triangulation
Introduction
A Brief Discussion on Swarm Intelligence
Battle Swarm Game Revisited
The Missile
The Battle Ship Defense
Building and Executing the Missile Genotypes
Analysis of the Complexity of Battle-Swarm
Identifying the Bottleneck
Method Description
Delaunay Triangulation
The Dynamic Layered Delaunay Triangulation (LDT)
Computation of the Swarm Neighborhood and Collision Table
Analysis of the Results
Conclusion
References
fulltext_6.pdf
Intelligent Solutions for Curve Reconstruction Problem
Introduction
Voronoi Diagram
Definition
Curves Are Captured by Delaunay Triangulations
Samples
Medial Axis
-Uniform Sample
-Sample
Approximate Medial Axis
Algorithms for -Uniform Samples
Euclidean Minimum Spanning Tree
-Shape
Algorithms for -Samples
-Skeleton
Crust
One-Step Crust
NN-Crust
Reconstruction of Closed Curves
TSP
Optimization-Based Algorithms
Concluding Remarks
References
fulltext_7.pdf
A Methodology for Automated Cartographic Data Input, Drawing and Editing Using Kinetic Delaunay/Voronoi Diagrams
Introduction
Introduction to the Voronoi Diagram of Points and Open Oriented Straight Line Segments
Quad-Edge Based Voronoi Data Structure
The Operations on the Dynamic Voronoi Data Structure
A Methodology for Raster to Vector Conversion of Colour Scanned Maps and Satellite Imagery
Skeletonization
Automated Approach to Skeletonization of Scanned Map Features
Results with Maps and Satellite Images
Kinetic Voronoi/Delaunay Drawing Tools
Map Drawing and Editing
An Integrated Approach
The Kinetic Point VD and Its Dual DT
The Kinetic Line-Segment VD
Robustness
Applications
Conclusions
References
fulltext_8.pdf
Density-Based Clustering Based on Topological Properties of the Data Set
Introduction
Motivation
Methodology
Cluster Analysis
Optimal Path in the Presence of Simple Disjoint Polygonal Obstacles
Optimal Path in a Varied Terrain
Voronoi Diagram for Optimal Path Planning
Outline of the Method
Methodology in Detail
Voronoi Diagram Construction
Generation of Roadmap
Dynamic Insertion and Deletion of Source and Destination
Removal of Redundant Vertices and Obtaining a Path with Minimum Number of Links
Iterative Refinement Using a Corner-Cutting Technique
Experimental Results
Conclusions
References
fulltext_9.pdf
Modeling Optimal Beam Treatment with Weighted Regions for Bio-medical Applications
Introduction
Theoretical Foundation
Region-to-Region Minimum Separation
A Prune-and-Search Approximation Scheme
A Simple Algorithm
Good Candidates and Acceptable Solutions
A Sum of Fractionals (SOF) Approximation Scheme
LinkSolver
Concluding Remarks
References
fulltext_10.pdf
Constructing Centroidal Voronoi Tessellations on Surface Meshes
Introduction
Background
Centroidal Voronoi Tessellations
Edge Collapse Simplification
Proposed Initialization Methods
Sizing Function Based Initialization
Ward's Method
Multi-start Method
Experimental Results
Conclusion
References
fulltext_11.pdf
Simulated Annealing and Genetic Algorithms in Quest of Optimal Triangulations
Introduction
On Triangulations
Simulated Annealing and Genetic Algorithms
Simulated Annealing for Optimal Triangulations
Genetic Algorithms for Optimal Triangulations
Generalization
Conclusion
References
fulltext_12.pdf
Higher Order Voronoi Diagrams and Distance Functions in Art and Visualization
Introduction
Bevels and Cushions
Emanations and Contours
Order-k Plots
Efficient Rendering
Texture
Sculpture and Iso-surfaces
Volume Rendering and Marching Cubes
Constructive Solid Geometry and Voronoi Based Approximations
Geometric Structures and Symmetry in Three Dimensions
Molecular Structures
Concluding Remarks
References
fulltext_13.pdf
Robust Point-Location in Generalized Voronoi Diagrams
Introduction
Point Location
Voronoi Diagrams
Algorithmic Degree
k-gon Voronoi Diagrams
Degree of Nearest Neighbor
Generalized Voronoi Diagram
Point Location Problem
Polyhedral Metric
The Algorithm
Polygonal Metric in the Plane
Conclusions
References
fulltext_14.pdf
Conclusions and Future Trends in Intelligent Treatment of Applied Problems
References
back-matter.pdf