Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean d-dimensional space

The problem of dynamic maintenance of a Voronoi diagram for a set of spheres moving independently in d-dimensional space is addressed in this paper. The maintenance of this Voronoi diagram for spheres moving along given trajectories, requires the calculation of topological events, that occur when d+...

Full description

Saved in:
Bibliographic Details
Published in:Computer aided geometric design 2003-07, Vol.20 (4), p.231-242
Main Authors: Gavrilova, M.L., Rokne, J.
Format: Article
Language:English
Subjects:
Applied sciences
Computer aided design
Computer science
control theory
systems
d-dimensional space
Euclidean metric
Exact sciences and technology
Generalized Voronoi diagram for spheres
Software
System of polydisperse spheres
Topological swap
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of dynamic maintenance of a Voronoi diagram for a set of spheres moving independently in d-dimensional space is addressed in this paper. The maintenance of this Voronoi diagram for spheres moving along given trajectories, requires the calculation of topological events, that occur when d+2 spheres become tangent to a common sphere. The criterion for determination of the topological event in the Euclidean metric is derived as a solution of a system of non-linear algebraic equations. The criterion is given in the form of polynomial algebraic equations dependent on the coordinates and trajectories of the moving spheres. These equations are solved using numerical methods. Application of the method to study the structure of a system of polydisperse spheres in a three-dimensional Euclidean space is briefly discussed.
ISSN:0167-8396
1879-2332
DOI:10.1016/S0167-8396(03)00027-X