L. J. Guibas and J. Stolfi, "Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams," ACM Trans. Graphics 4 (1985), 74--123 .  Home/Search   Document Not in Database   Summary   Related Articles   Check

....examine the problem in external memory for two and three dimensions. The three dimensional case is particularly interesting because of the number of twodimensional geometric structures closely related to it, such as Voronoi diagrams and Delaunay triangulations. In fact, by well known reductions [17], our 3 d convex hull algorithm immediately gives externalmemory algorithms for planar Voronoi diagrams and Delaunay triangulations with the same I O performance. In main memory the lower bound for computing the convex hull of N points in dimension d = 2 and d = 3 is Omega Gamma N log N ) 30] ....

L. J. Guibas and J. Stolfi, "Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams," ACM Trans. Graphics 4 (1985), 74--123 .

....k = 1; ffi TRI . Theorem 3.6. There is an implementation of ReverseSearch2(Adj TRI , ffi TRI , S TRI , f TRI ) for the triangulation enumeration problem with time complexity O(n jV TRI j) and space complexity O(n) Proof. For the implementation, we can use the quad edge data structure [13] for storing a triangulation. Also we store L as a linked list of edges each with a flag indicating either nonflippable, legal or illegal, and store the lexico smallest illegal edge of L. For the analysis of time complexity, we apply Theorem 2.4. First, note that we can evaluate Adj TRI and f TRI ....

L.J. Guibas and J. Stolfi, "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams," ACM Trans. Graphics 4 (1985), 74-123. 20

.... (circumcircle) of each triangle contains no vertices in its interior [71] Delaunay triangulations of m points can either be computed whole, using divideand conqueror sweepline algorithms, or incrementally, by inserting vertices one at a time, updating the triangulation after each insertion [48]. The former approach has cost O(m logm) while the latter, incremental method has worst case cost of O(m 2 ) Typical costs for the incremental approach are much better than quadratic, however. 6 Figure 1: Top view of a regular grid triangulation of 65 65 height field. Figure 2: A ....

Leonidas Guibas and Jorge Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2):75--123, 1985.

....be obtained in linear time from the Delaunay triangulation, using the one one correspondence between their faces. See [5, 13, 15, 16] for more citations. 4 algorithm d worst case uniform citation flipping 2 O(n 2 ) Chapter XXX plane sweep 2 O(n log n) divide and conquer 2 O(n log n) O(n) [17, 19] randomized incremental 2 O(n log n) randomized incremental 3 O(n dd=2e ) O(n log n) gift wrapping 2 O(n dd=2e 1 ) O(n) 12] Figure 3: Delaunay triangulation algorithms in the Euclidean metric for point sites. The randomized incremental algorithm The incremental algorithm adds sites one ....

L.J. Guibas, J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics 4(2):74--123, 1985.

....arithmetic in divide and conquer planar Delaunay triangulation, as a function of interpolation parameter OE. generated by a non random process, and so contain many degeneracies. 6. 1 Delaunay Triangulations We experimented with the divide and conquer algorithm for planar Delaunay triangulations[18]. The required primitives are the orientation test and incircle test (both in two dimensions) If points are represented with affine coordinates, these primitives have degrees 2 and 4, respectively. Each input data set consisted of 10000 points with 53 bit integer coordinates. Input sites were ....

L. J. Guibas, J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics 4(2):74-123, 1985.

No context found.

L.J. Guibas, J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics 4(2):74-- 123, 1985.

Documents 101 to 150  Previous 50  Next 50

Online articles have much greater impact   More about CiteSeer   Add search form to your site   Submit documents   Feedback  


CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute