Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean \(d\)-dimensional space. (English) Zbl 1069.65554
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 nonlinear 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.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
generalized Voronoi diagram for spheres; \(d\)-dimensional space; topological swap; system of polydisperse spheres; Euclidean metricReferences:
| [1] | Albers, G.; Guibas, L. J.; Mitchell, J. S.B.; Roos, T., Voronoi diagrams of moving points, Internat. J. Comput. Geom. Appl., 8, 365-380 (1998) · Zbl 1035.68520 |
| [2] | Atallah, M., Some dynamic computational geometry problems, Comput. Math. Appl., 11, 1171-1181 (1985) · Zbl 0586.68085 |
| [3] | Aurenhammer, F.; Klein, R., Voronoi diagrams, (Sack, J.; Urrutia, J., Handbook of Computational Geometry (2000), Elsevier: Elsevier Amsterdam) · Zbl 0995.65024 |
| [4] | Boissonnat, J.-D.; Yvinec, M., Algorithmic Geometry (1998), Cambridge University Press · Zbl 0917.68212 |
| [5] | Devillers, O.; Golin, M.; Kedem, K.; Schirra, S., Revenge of the dog: queries on Voronoi diagrams of moving points, (Proc. of the 6th Canadian Conference on Computational Geometry (1994)), 122-127 |
| [6] | Dey, T. K.; Sugihara, K.; Bajaj, C. L., DT in three dimensions with finite precision arithmetic, Computer Aided Geometric Design, 9, 457-470 (1992) · Zbl 0762.65110 |
| [7] | Edelsbrunner, H.; Shah, N., Incremental topological flipping works for regular triangulations, Algorithmica, 15, 223-241 (1996) · Zbl 0840.68050 |
| [8] | Fink, E.; Wood, D., Restricted-orientation halfspaces, (Proceedings of the Vision Geometry V Conference (1996)), 24-33 |
| [9] | Fu, J.; Lee, R., Voronoi diagrams of moving points in the plane, Internat. J. Comput. Geom. Appl., 1, 1, 23-32 (1991) · Zbl 0724.68087 |
| [10] | Gavrilova, M.; Rokne, J., Collision detection optimization in a multi-particle system, (Lecture Notes in Computer Science, 2331 (2002), Springer-Verlag: Springer-Verlag Berlin), 105-114 · Zbl 1049.68782 |
| [11] | Gavrilova, M., Robust algorithm for finding nearest-neighbors under \(L\)−\(1, L\)-inf and power metrics in the plane, (Lecture Notes in Computer Scie., 2073 (2001), Springer-Verlag: Springer-Verlag New York), 663-672 · Zbl 0982.68706 |
| [12] | Gavrilova, M.; Rokne, J., Swap conditions for dynamic VD for circles and line segments, Computer Aided Geometric Design, 16, 89-106 (1999) · Zbl 0909.68186 |
| [13] | Gupta, P., Janardan, R., Smid, M., 1994. Fast algorithms for collision and proximity problems involving moving geometric objects. Report MPI-I-94-113, Max-Planck-Institut fur Informatik, Saarbrücken; Gupta, P., Janardan, R., Smid, M., 1994. Fast algorithms for collision and proximity problems involving moving geometric objects. Report MPI-I-94-113, Max-Planck-Institut fur Informatik, Saarbrücken |
| [14] | Hiyoshi, H.; Sugihara, K., Voronoi-based interpolation with higher continuity, (Proceedings of the 16th Annual Symposium on Computational Geometry (2000), ACM), 242-250 · Zbl 1378.65058 |
| [15] | Hubbard, P., Approximating polyhedra with spheres for time-critical collision detection, ACM Trans. Graph., 15, 3, 179-210 (1996) |
| [16] | Kobayashi, K.; Sugihara, K., Crystal growth Voronoi diagram and its applications to collision-free paths, (Lecture Notes in Computer Science, 2073 (2001), Springer-Verlag: Springer-Verlag New York), 738-747 · Zbl 0982.68605 |
| [17] | Kim, D.-S.; Kim, D.; Sugihara, K.; Ryu, J., Voronoi diagram of a circle set from Voronoi diagram of a point set: I. Topology, Computer Aided Geometric Design, 18, 541-562 (2001) · Zbl 0969.68161 |
| [18] | Kim, D.-S.; Kim, D.; Sugihara, K.; Ryu, J., Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry, Computer Aided Geometric Design, 18, 563-585 (2001) · Zbl 0969.68162 |
| [19] | Luchnikov, V. A.; Gavrilova, M. L.; Medvedev, N. N.; Voloshin, V. P., The Voronoi-Delaunay approach for modeling the packing of balls in a cylindrical container, (Future Generation Computer Systems, Special Issue on Computer Modeling, Algorithms and Supporting Environments, 18 (2002), Elsevier: Elsevier Amsterdam), 673-679 · Zbl 1042.68110 |
| [20] | Okabe, A.; Boots, B.; Sugihara, K., Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (1992), Wiley: Wiley Chichester, pp. 205-208 · Zbl 0877.52010 |
| [21] | Roos, T., Voronoi diagrams over dynamic scenes, Discrete Appl. Math., 43, 3, 243-259 (1993) · Zbl 0770.68115 |
| [22] | Schaudt, B.; Drysdale, R., Higher-dimensional Voronoi diagrams for convex distance functions, (Proceedings of the 4th Canadian Conference on Computational Geometry (1992)), 274-279 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
