L. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. AMC Trans. Graphics, 4(2):74--123, 1985.  Home/Search   Document Not in Database   Summary   Related Articles   Check

....former position idx in the stack and two offset values (see Figure 1) are stored with the label. The new active gate is the previous edge along the boundary from the stack. An example run for the encoding and the decoding process is given in Figure 2 and 3. We use an enhanced half edge structure [3] during encoding and decoding to store the mesh connectivity and to maintain the boundaries. Besides pointers to the origin, to the next and the previous edge around the origin, and to the invers halfedge, we have two pointers to reference a next and a previous boundary edge. This way we organize ....

L. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computationof Voronoi Diagrams. ACM Transactions on Graphics, 4(2):74--123, 1985.

....sites. The algorithm has been effectively coded and experimental results are given. 1 Introduction The Delaunay triangulation and its dual, the Voronoi diagram, are subjects of major interest in Computational Geometry. A lot of algorithms compute it in optimal Omega Gamma n log n) time [24, 15, 14, 11, 21]. But these algorithms are rather complicated and difficult to implement effectively, so the sub optimal algorithm [12] is often preferred. Furthermore, this algorithm is on line and does not impose to compute again the whole triangulation at each insertion. In the last few years some simpler ....

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

....free or not (a free face is guaranteed to appear on the union boundary) The complexity of the arrangement A i is evidently O(1) For each ball in M , the above procedure will take O(1) time. In Step 3 we will represent the outer connected component of the union boundary by a quad edge structure [13]. To this end we have to augment the arrangements A i slightly. If A i is the whole sphere S i we split it into two parts with some circle. Next, 12 if a boundary component of A i is a simple circle C we split C into two arcs adding two vertices. If C lies in both A i and A j the same vertices ....

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

....shared vertex data structure, if the neighborhood information is not stored explicitly. Several data structures have been developed to provide fast access (ideally O(1) to the information that is required by different algorithms. The most popular ones are the wingededge [Bau72] quad edge [GS85], and half edge [Mae88] data structures. Fig. 3 shows the winged edges according to O Rourke [O R95] Each vertex stores its geometric position and 2 v a v b f b f a e a e b e c e d x 0 y 0 z 0 e 0 x 1 y 1 z 1 e 1 Vertices v i e 0 e 1 e 2 e 3 e 4 Faces f ....

Leonidas Guibas and Jorge Stolfi. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics, 4(2):74--123, April 1985.

....two opposite halfedges, which makes this access less efficient. The Minimal Rendering Tool MRT [2] uses a halfedge data structure for polygonal surfaces. Quad Edge Data Structure. Similar to the idea for halfedges, each edge is split into four quad edges to obtain the quad edge data structure [12]. It provides a fully symmetric view on the primal and the dual graph, as can be seen in Figure 6. Instead of using opposite pointers, a two bit counter r is used to address a slot in an edge record e of four quad edges. This data structure is able to model non orientable 2 manifolds with an ....

L. Guibas and J. Stolfi. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transaction on Graphics, 4(3):74--123, July 1985.

....issues. Examples include the development of a theory of oriented projective geometry[89] representations of spatial subdivisions in general dimension[10, 62] perturbation schemes that symbolically eliminate degeneracies[34] and careful analysis of the details of fundamental algorithms[54]. However, it takes a good deal of sophistication to pick and choose among offered algorithms, and then to know what implementation suggestions are relevant. This chapter samples recent research in computational geometry. Rather than attempt a comprehensive survey, the chapter considers three ....

....method is to randomize an incremental algorithm. Incremental algorithms are often very simple: objects are inserted one by one with the desired structure updated after each addition; a classic example is the incremental computation of a Delaunay triangulation or a Voronoi diagram in two dimensions[48, 54]. An objection to incremental algorithms is that if the insertion order is chosen badly, then each addition requires a lengthy update to the structure, and the algorithm runs slowly. A remarkable discovery for some problems is that if objects are inserted in random order, then the expected work at ....

[Article contains additional citation context not shown here]

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.

....[1] computer vision [2] and mesh generation [3] Its property of producing triangulations with well shaped triangles makes it particularly appropriate for subsequent analysis techniques such as finite element methods. Many algorithms for computing Delaunay triangulations are known, including [4, 5, 6, 7]. Some of these construct a supertriangle surrounding the points to be triangulated [5, 7] insert the points incrementally into the triangulation, then remove the supertriangle and all edges from it. Sloan and Houlsby note that boundary of the triangulation produced may be locally concave [8] ....

.... well shaped triangles makes it particularly appropriate for subsequent analysis techniques such as finite element methods. Many algorithms for computing Delaunay triangulations are known, including [4, 5, 6, 7] Some of these construct a supertriangle surrounding the points to be triangulated [5, 7], insert the points incrementally into the triangulation, then remove the supertriangle and all edges from it. Sloan and Houlsby note that boundary of the triangulation produced may be locally concave [8] They suggest that this effect may be reduced by suitable choice of supertriangle points, and ....

[Article contains additional citation context not shown here]

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

....5 Computed Examples The algorithm from Section 4.3 is implemented in C and executed on an SGI Indigo2 workstation with a 200 Mhz MIPS R4400 processor. The computation times and other parameters for several examples are listed in Figure 11. The implementation uses the quadedge structure from [8] to maintain the topological ordering of the regions. The information graph G I is searched using Dijkstra s shortest path algorithm, where the edge cost is taken as the distance between adjacent cell centroids. The solution is computed by traversing from cell centroid to cell centroid, causing ....

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

No context found.

L. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2):74--123, April 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.

No context found.

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.

No context found.

Guibas, Leonidas, and Stol, Jorge, Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams, ACM Transactions on Graphics, Vol. 4, No. 2, 1985, 74-123.

Documents 51 to 100  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