Leonidas Guibas
ABSTRACT
The computation of Delaunay triangulations from static point sets has been extensively studied in computational geometry. When the points move with known trajectories, kinetic data structures can be used to maintain the triangulation. However, there has been little work so far on how to maintain the triangulation when the points move without explicit motion plans, as in the case of a physical simulation. In this paper we examine how to update Delaunay triangulations after small displacements of the defining points, as might be provided by a physics-based integrator. We have implemented a variety of update algorithms, many new, toward this purpose. We ran these algorithms on a corpus of data sets to provide running time comparisons and determined that updating Delaunay can be significantly faster than recomputing.
- M. Abellanas, F. Hurtado, and P. A. Ramos. Structural tolerance and Delaunay triangulation. Information Processing Let-ters, 71(5-6):221--227, 1999. Google Scholar
Digital Library
- N. Amenta and M. W. Bern. Surface reconstruction by voronoi filtering. In Symp. on Comp. Geom., pages 39--48, 1998. Google ScholarDigital Library
- N. Amenta, S. Choi, and G. Rote. Incremental constructions con BRIO. In Proc. of the 19th conference on Comp. geometry, pages 211--219, 2003. Google ScholarDigital Library
- D. Attali, J.-D. Boissonnat, and A. Lieutier. Complexity of the delaunay triangulation of points on surfaces the smooth case. In Proc. of the 19th conference on Comp. geometry, pages 201--210. ACM Press, 2003. Google ScholarDigital Library
- F. Aurenhammer. Power diagrams: properties, algorithms, and applications. SIAM J. on Computing, 16:78--96, 1987. Google ScholarDigital Library
- D. Bandyopadhyay and J. Snoeyink. Almost-Delaunay simplices: Nearest neighbor relations for imprecise points. In ACM-SIAM Symp. on Discrete Algorithms, pages 403--412, 2004. Google ScholarDigital Library
- J. Basch, L. Guibas, and J. Hershberger. Data structures for mobile data. In ACM-SIAM Symp. on Discrete Algorithms, pages 747--756, 1997. Google ScholarDigital Library
- J. Basch, L. J. Guibas, and J. Hershberger. Data structures for mobile data. In ACM-SIAM symp. on discrete algorithms, pages 747--756. Society for Industrial and Applied Mathematics, 1997. Google ScholarDigital Library
- J. Basch, L. J. Guibas, C. D. Silverstein, and L. Zhang. A practical evaluation of kinetic data structures. In Proc. of the 13th annual symp. on Comp. geometry, pages 388--390, 1997. Google ScholarDigital Library
- P. Cignoni, C. Montani, and R. Scopigno. A fast divide and conquer Delaunay triangulation algorithm in Ed. Computer Aided Design, 30:333--341, 1998.Google ScholarCross Ref
- O. Devillers. Improved incremental randomized Delaunay triangulation. In Proc. of the 14th annual symp. on comp. geometry, 1998. Google ScholarDigital Library
- O. Devillers and S. Pion. Efficient exact geometric predicates for delaunay triangulations. In Proc. 5th Workshop Algorithm Engineering Experiments, pages 37--44, 2003.Google Scholar
- O. Devillers and M. Teillaud. Perturbations and vertex removal in a 3d Delaunay triangulation. In ACM-SIAM symp. on Discrete algorithms, pages 313--319. Society for Industrial and Applied Mathematics, 2003. Google ScholarDigital Library
- H. Edelsbrunner. The union of balls and its dual shape. Discrete Comp. Geom., 13:415--440, 1995.Google ScholarDigital Library
- H. Edelsbrunner and P. Koehl. The weighted volume derivative of a space-filling diagram. In Proc. of the National Academy of Science, volume 100, pages 2203--2208, 2003.Google ScholarCross Ref
- H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements. In Proc. of the 1st annual symp. on comp. geometry, pages 251--262. ACM Press, 1985. Google ScholarDigital Library
- H. Edelsbrunner and N. R. Shah. Incremental topological flipping works for regular triangulations. In Proc. of the 8th annual symp. on comp. geometry, pages 43--52. ACM Press, 1992. Google ScholarDigital Library
- J. Erickson. Local polyhedra and geometric graphs. In Proc. of the 19th annual conference on Comp. geometry, pages 171--180. ACM Press, 2003. Google ScholarDigital Library
- J. Erikson. Dense point sets have sparse Delaunay triangulations. In ACM-SIAM Symp. on Discrete Algorithms, pages 125--134, 2002. Google ScholarDigital Library
- G. D. Fabritiis and P. V. Coveney. Dynamical geometry for multiscale dissipative particle dynamics. arXiv:cond-mat: 0301378.Google Scholar
- J. Gao, L. Guibas, and A. Nguyen. Deformable spanners and their applications. 2004.Google Scholar
- M. Gavrilova and J. Rokne. Collision detection optimization in a multi-particle system. International Workshop on Comp. Geom. and Applications, 2331:105--114, 2002. Google ScholarDigital Library
- GNU scientific library. http://www.gnu.org/software/gsl/.Google Scholar
- E. Guendelman, R. Bridson, and R. Fedkiw. Nonconvex rigid bodies with stacking. ACM Transactions on Graphics, 22(3):871--878, 2003. Google ScholarDigital Library
- L. Guibas. Kinetic data structures: A state of the art report. In Proc. 3rd Workshop on Algorithmic Foundations of Robotics, 1998. Google ScholarDigital Library
- L. Guibas and M. Karavelas. Interval methods for kinetic simulations. In Proc. of the 15th annual symp. on comp. geometry, pages 255--264, 1999. Google ScholarDigital Library
- L. Guibas, M. Karaveles, and D. Russel. A comp. framework for handling motion. In ALENEX 2004, Lecture notes in Computer science, 2004. to appear.Google Scholar
- L. Guibas, D. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7:381--413, 1992.Google ScholarDigital Library
- L. Guibas, A. Nguyen, D. Russel, and L. Zhang. Collision detection for deforming necklaces. In Proc. of the 18th annual symp. on comp. geom, pages 33--42. ACM Press, 2002. Google ScholarDigital Library
- L. J. Guibas and L. Zhang. Euclidean proximity and power diagrams. In Canadian Conference on Comp. Geom., pages 90--91, 1998.Google Scholar
- B. Joe. Three-dimensional triangulations from local transformations. SIAM J. on Scientific and Statistical Computing, 10:718--741, 1989. Google ScholarDigital Library
- J. R. Shewchuk. A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations. In Proc. of the 14th annual symp. on Comp. geometry, pages 76--85, 1998. Google ScholarDigital Library
- P. Su and R. L. D. III. A comparison of sequential Delaunay triangulation algorithms. In Proc. of the 11th annual symp. on Comp. Geom., pages 61--70, 1995. Google ScholarDigital Library
- Tinker molecular simulation package. http://dasher.wustl.edu/tinker/.Google Scholar
- R. C. Whaley, A. Petitet, and J. Dongarra. Automated empirical optimizations of software and the ATLAS project. Parallel Computing, 27(1-2):3--35, 2001.Google ScholarDigital Library
Index Terms
- An empirical comparison of techniques for updating Delaunay triangulations
Recommendations
Conforming weighted delaunay triangulations
Given a set of points together with a set of simplices we show how to compute weights associated with the points such that the weighted Delaunay triangulation of the point set contains the simplices, if possible. For a given triangulated surface, this ...
Flips in Higher Order Delaunay Triangulations
LATIN 2020: Theoretical InformaticsAbstractWe study the flip graph of higher order Delaunay triangulations. A triangulation of a set S of n points in the plane is order-k Delaunay if for every triangle its circumcircle encloses at most k points of S. The flip graph of S has one vertex for ...
Incrementally constructing and updating constrained Delaunay tetrahedralizations with finite-precision coordinates
Constrained Delaunay tetrahedralizations (CDTs) are valuable for discretizing three-dimensional domains with constraints such as edges and polygons. But they are difficult to generate and maintain robustly when finite-precision coordinates yield ...
Reviews
Patrick J. Ryan
Efficient techniques for computing the Voronoi diagram and Delaunay triangulation for a finite set of points in Euclidean space E d are well known. This paper is concerned with the problem of computing the Delaunay triangulation D(P') of a perturbed point set P' when the original point set P and its Delaunay triangulation D(P) are given. Of course, an underlying assumption is that the amount by which P' differs from P is small, so that D(P') can be expected to share much of its combinatorial and topological structure with D(P) . As the title indicates, this paper is a report on empirical research comparing various algorithms for solving this problem in E 3. Two basic approaches are compared: kinetic and static. In the kinetic approach, a specific interpolation method is chosen, and the data structure is updated at events, occurring when some pair of adjacent cells no longer satisfies the necessary local criterion for being Delaunay (the "InCircle" condition, though actually "InSphere" would be more appropriate terminology in three dimensions). In the static approach, only the initial and final configurations are considered, and the algorithms use some combination of point removal and flipping on pairs of adjacent cells that do not satisfy InCircle. For each approach, various ways of setting up the algorithms are discussed (for example, how to interpolate, and when to use point removal or flipping). These are rather technical, and are not fully specified in the paper, but relevant references to other sources are given. Readers who are familiar with such techniques will find the results of the authors' extensive tests interesting. The authors discuss which parts of the computations are most costly, and where improvements might be possible. Their results show that, generally speaking, the kinetic approaches are not currently competitive with the static approaches. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments