Guibas, L., Stolfi, J. (1985): Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics, 4(2), 75--123 For information concerning the source code please contact the first author  Home/Search   Document Not in Database   Summary   Related Articles   Check

....constraints. A CDT can be seen as the triangulation closest to the DT that respects given constraints. The computation of the DT of a set of points in R is a classical problem in computational geometry [15] Asymptotically optimal algorithms are known, as the O(n log n) divide and conquer [12] and sweepline [9] algorithms. For CDTs, an optimal O(n log n) divide and conquer algorithm is also known [5] However the most popular implementations for both DT and CDT are those which are incremental and do not require the use of complicated data structures in addition to the triangulation ....

....computation restarts. Data structure. The algorithms we will present require the triangulation to be represented by an e#cient data structure, i.e. capable to give all adjacency relations in constant time. We implemented a data structure following the adjacency strategy of the quad edge structure [12] and integrating element lists and operators as in the half edge structure [27] Our basic element is a structure representing an oriented edge. Each oriented edge is associated with only one vertex, one edge and one face. We call this basic element a SymEdge. This name is due to the fact that ....

[Article contains additional citation context not shown here]

Guibas, L., Stolfi, J. (1985): Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics, 4(2), 75--123 For information concerning the source code please contact the first author

....Maximizes the economic e#ciency of a community of power consumers [27] TreeAdd: Sums the val es of the nodes in a binary tree using a recursive depth first traversal . TSP: Sol es the travel9 g sal74II probl em [24] Vorono i : Computes a Voronoi diagram for a random set of points [17]. We do not incl ude resul ts for TSP because it uses a nondeterministic, probabil9S ic al940I hm, causing the number of write barriers executed to be vastl y di#erent in each run of the same executabl e. We present resul ts for the fol l owing compil er options: Baseline: No optimization, al ....

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, 1985.

....in the graph. An adjacency list improves on the space requirements for storing graphs vith fev edges: each vertex of the graph has a list of its adjacent vertices. Once a graph is embedded, the order in vhich edges enter a vertex determines the faces of the graph. The winged edge [7] or quad edge [46] data structures capture this information. Both structures are edge based, meaning that they explicitly store the edges of the graph, and use comparable amounts of storage space. The vinged edge data structure is similar to a doubly linked list. Each edge keeps a reference to the next clocksvise ....

....bounds face u and v in G. There is a bijection betveen the edge sets E and E (Figure 2. 5) The graph G is the primal graph and G is its dual graph [9] The quad edge data structure simultaneously represents the primal and dual aspects (vertices and faces) of the graph in a symmetric man ner [46]. We expand on duality in Section 2.7 vhen ve describe Voronoi diagrams and Delaunay triangulations. As vith the vinged edge data struc ture, each edge in the quad edge data structure keeps a reference to the next counterclockvise edge around its endpoints. For each edge e, there is a dual ....

[Article contains additional citation context not shown here]

L. J. Gulbas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronol diagrams. ACM Trans. Graph., 4(2):74-123, Apr. 1985.

....but the global non interference conditions on cells are not enforced automatically and must be checked. A variety of other, similar in spirit, manifold boundary representations have been proposed in efforts to optimize the space, ease of manipulation, or handling of specific geometric carriers[23, 28, 132]. Boundary representations for non manifold solids can be designed directly as representations of 2 cycles in Euclidean space or by treating the boundary of a non manifold solid as a union of manifold shells. Both approaches also apply to boundary representations of arbitrary heterogeneous ....

....Euler operators are necessary and sufficient to span the space of all such cell complexes. Euler operators conveniently enforce the required combinatorial conditions on such cell complexes, but they are not unique, and other approaches to constructing and maintaining ordering are possible [28]. 4.2. Enabling algorithms All other geometric queries and algorithms in solid modeling may be constructed using sequences of the above fundamental computations. It would be impractical to describe here all algorithms important in solid modeling, but it is instructive to consider how some of the ....

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

....locally optimum solution. 3. 1 Notation We use bold faced letters to distinguish a vector from a scalar value (e.g. the origin, o) We assume that the model (a convex polytope in our case) is triangulated and its topological representation is precomputed using such as the quad edge data structure [34]. Moreover, we use V, E and F, respectively, to denote a vertex, an edge and a face of a polytope. In particular, we use (V,V) to denote the vertex hub pair which plays a key role in our incremental algorithm to be explained in Section 3.3. However, we use italic letters to distinguish a ....

Leonidas J. Guibas and J. Stolfi, "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams," ACM Trans. Graph., vol. 4, no. 2, pp. 74--123, Apr. 1985.

....framework for handling triangle (tetrahedron) insertion and removal into unstructured meshes becomes an important issue. Effective representation of unstructured meshes is also critical, and several data structures to represent and manipulate them have been published over the years [5] 6][7]. Such structures usually offer efficient solutions to represent and recover mesh topology and modify its geometric parameters. To insert new elements into the mesh, or to remove existing elements, some data structures define operators that ensure the topological consistency of the resulting mesh ....

....not discuss topological operators to manage the data structures presented. Some topological data structures became popular in the context of two dimensional mesh generation and representation. The winged edge by Baumgart [8] the half edge by M ntyli [12] and the quad edge by Guibas and Stolfi [7] are well known examples that use topological operators to maintain mesh consistency (incidence and adjacency) and topological control. To manipulate the quad edge data structure Guibas and Stolfi [7] present a single topological operator, the Splice. Baumgart [8] and Mintyli [12] utilize a set of ....

[Article contains additional citation context not shown here]

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

....to an open disk. A3) The surface # is connected. Condition (A1) above makes sure that no information is lost due to self occlusion in the process of projecting the rim onto the apparent contour, while (A2) restricts the rim mesh to the computationally convenient form of a simple subdivision [18]. In particular, it can be Note that even though the structure of the rim mesh depends only on the camera centers O 1 , O n , we actually need to know the complete camera matrices in order to compute the epipolar geometry between pairs of views. 113 shown [18, Theorem 1.1] that the ....

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

....the position of the node v i . Here, D is the set of distances q j is the set of triangular faces with the corresponding set of areas A a defined by a ijk = det x i y i 1 x j y j 1 x k y k 1 = q k q i ) 3) S = 1 0 . 4) We use Delaunay triangulation [17, 18, 19] of a set of points to obtain our triangulated graphs. In Figure 1 a triangulated V formation is shown with 2, 3, 4, 5, 6, 7 , 21, 31, 32, 42, 43, 53, 54, 64, 65, 75, 76 , 312, 432, 534, 654, 756 . 5) 1 2 3 4 5 6 7 Figure 1: A triangulated V formation. Fix the edge and ....

L. Gubias and J. Stolfi, "Primitives for the manipulation of general subdivisions and the computation of voroni diagrams," ACM Trans. on Graphics, vol. 4, no. 2, pp. 74--123, April 1985. 11

....algorithmic a programmer needs to know to implement a state of the art triangular mesh generator for straight line domains. Curved boundaries and surfaces, however, are not treated here. Thorough treatments of data structures and Delaunay triangulation algorithms are available elsewhere [17, 29, 7]. A full description of the mesh generation problem begins with the domain to be meshed. Most theoretical treatments of meshing take as their input a planar straight line graph (PSLG) A PSLG is a set of vertices and segments, like that illustrated in Figure 1(a) A segment is an edge that must ....

....The act of inserting a vertex to improve poor quality triangles in one part of a mesh will not unnecessarily perturb a distant part of the mesh that has no bad triangles. Furthermore, Delaunay triangulations have been extensively studied, and good algorithms for their construction are available [21, 17, 15, 7]. The greatest advantage of Delaunay triangulations is less obvious. The central question of any Delaunay refinement algorithm is, Where should the next vertex be inserted As Section 2 will demonstrate, a reasonable answer is, As far from other vertices as possible. If a new vertex is ....

Leonidas J. 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.

....interior vertices with none. Finally, a boundary triangulated 2 mnifold or BTM is a simplicial complex in which all vertices are boundary vertices. Figure I depicts two simplicial complexes; the second is a BTM. Simplicial complexes can be represented by Guibas and Stolfi s quad edge structure [23], by Baumgart s winged edge structure [3] or by their dual graph. We require that each triangle be able to access its edges and each edge its incident triangles in constant time. If a polygonal region is given, we can triangulate it in O(nlog n) time by a sweepline algorithm [35] or, if there are ....

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, 1985. 27

....V. Theorem 3.2 Let V be a set of n points in the plane. One can determine for each point in V its nearest neighbor in V in time O(nlog n) Using Voronoi diagrams is very practical. The algorithms to construct them are not hard to implement (although they might look that way) Guibas and Stolfi [36] show how to do this implementation. Another approach is to use a quite different method (using the plane sweep technique) that was designed by Fortune [30] 3.2 Delaunay triangulation Let V be a set of points. We call two points neighbors when their Voronoi regions share an edge. Now assume ....

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

....# Power: Maximizes the economic eciency of a communityofpower consumers [27] # TreeAdd: Sums the values of the nodes in a binary tree using a recursive depth rst traversal. # TSP: Solves the traveling salesman problem [24] # Voronoi: Computes a Voronoi diagram for a random set of points [17]. We do not include results for TSP because it uses a nondeterministic, probabilistic algorithm, causing the number of write barriers executed to be vastly di erentineach run of the same executable. We present results for the following compiler options: # Baseline: No optimization, all ....

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

....is unlabelled, e is the corresponding directed edge in M; otherwise, e is the directed joined edge in M with a directed initial segment corresponding to e in T. Encoding and decoding times are O(m) given, e.g. the adjacency list representation of [Keeler95] or the quad edge data structure [Guibas85]. In encoding, O(m) time is taken to choose S, traverse T emitting symbols and compute labels for T using a copy of M (remove each successive non tree edge e adjacent to the unbounded region; e CCW about the unbounded region opposes e CCW about the circuit made by e and elements of S) In ....

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

....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 triangu lations. 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 perfor malice. In main memory the lower bound for computing the convex hull of iv points in dimension d 2 and d 3 is i(ivlogiv) 30] In ....

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

....du site supprimer. L algorithme a t effectivement programm et des rsultats exprimentaux sont fournis. 1 Introduction The Delaunay triangulation and its dual, the Vorono diagram, are subjects of major interest in Computational Geometry. A lot of algorithms compute it in optimal fl(tzlogtz) time [23,14,13,10,20]. But these algorithms are rather complicated and difficult to implement effectively, so the sub optimal algorithm [11] 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 subdivi- sions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2):74 123, April 1985.

....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 triangula tions. 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 perfor mance. In main memory the lower bound for computing the convex hull of N points in dimension d 1 is (N log N) in the worst case [a0] In ....

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

....triangle of #( K contains # 1 (q) or, equivalently, which triangle of #(#( K ) contains q. This is a standard point location problem in an irregular triangulation. We use the point location algorithm of Brown and Faigle [2] which avoids looping that can occur with non Delaunay meshes [10, 9]. Once we have found the triangle j, k which contains q, we can write q as q = #(p i) # #(p #(pk and thus # 1 (q) p ) Figure 10 shows the result of this procedure: a level 3 uniform remeshing of a 3 holed torus using the # 1 map. A note on complexity: The point location ....

GUIBAS, L., AND STOLFI, J. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics 4, 2 (April 1985), 74--123.

....[1, 16, 54] Various approaches for their con struction are described in the literature. Naturally, it was the planar case, which was solved first, but extensions to 3 and higher dimensions followed. Incremental methods (for example [4, 39] compete with divide and conquer algorithms (for example [8,42]) Newer research studies randomization [41] One approach uses a lifting map (see below) to transform the triangulation problem in R to the problem of constructing the convex hull in R . This idea goes back to [7] details on the con structions of convex hulls in d dimensions can be found in ....

....Karasick, Lieber, and Nackman [47] use daptive precision arithmetic for computing the sign of determinants with integer or rational el ements. They use these method to implement two dimensional Delaunay triangulations employing the popular divide and conquer algorithm of Guibas and Stolfi [42]. They provide empirical tests and claim a factor of 4 for the computational overhead with respect to unstable floating point im plement ations. A more rigorous approach is to not only tackle the numerical problems by using exact arithmetic but also cope with degeneracies as such by using a ....

[Article contains additional citation context not shown here]

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

....torus, and the Klein bottle. Basic Definitions This chapter is based on books of White [Whi73] Ringel [Rin74] Bollobas [Bol78] Even [Eve79] Tutte [Tut84] Gross and Tucker [GT87] Bredon [Bre93] Schmidt and Strohlein [SS93] and Henle [Hen94] as well as on articles of Guibas and Stolfi [GS85] Archdeacon [Arc96] and Ellingham [Ell96] In Section 2.1 we introduce basic graph theoretic notations used in this thesis and Section 2.2 provides background to elementary topology in Section 2.2. In Section 2.3 we bring together graph theory and topology for describing embeddings, especially ....

....the algorithm presented in Chapter 5. Therefore we do not present it in Part I Algorithms for Bounded Degree Spanning Trees . New Results We further simplify the data structures used by Giammarresi and Italiano [GI96] They are based on the planar subdivision primitives of Guibas and Stolfi [GS85] see also Section 2.3) We introduce a new abstract data structure IncidenceDS to maintain the incidence relation between the vertices and faces of a plane graph during the edge deletions. Implementing this incidence data structure by different means, we get different total update time for all ....

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, 1985.

.... The algorithm is a straightforward adaptation of the plane sweep paradigm to the sphere and its running time is O( m n ) log n) Its output is a data structure that allows for a traversal of the arrangement cell by adjacent cell (we could use, say, the quadedge data structure for the purpose [10]) If we are only concerned with worst case running time, and since the complexity of the arrangement A(Q) can be Theta(n in the worst case (see below) we can compute the arrangement in Theta(n ) time by substituting each arc in Q by the great circle containing it and computing the ....

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

.... also use here a randomized incremental construction algorithm whose expected running time is O(n log n m) see, e.g. 20] Its output is a data structure that allows for a traversal of the arrangement face by adjacent face (we could use, say, the quad edge data structure for the purpose [12]) If we are only concerned with worst case running time, and since the complexity of the arrangement A(Q) can be (n ) in the worst case (see below) we can compute the arrangement in (n ) time by substituting each arc in Q by the great circle containing it and computing the arrangement ....

Leonidas J. Guibas and J. Stol . Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph., 4:74-123, 1985.

....nor have large circumcircle, are identified. d) The identified triangles are added to the mesh. failure is dealt with by changing the orientation of the associated boundary edge to ensure correct behavior. Triangulate Figure 8 (b) shows an example of a two dimensional Delaunay triangulation [16, 12]. Note that it may contain triangles that are outside of a boundary edge (see Figure 8 (c) These are removed to preserve the cookie cutter outline of the neighborhood that was originally removed from the mesh. After this cleanup the triangles are ready to be reinserted into the original mesh ....

GUIBAS, L., AND STOLFI, J. Primitives for the manipulation of general subdivisions and computation of voronoi diagrams. ACM Transactions on Graphics 4, 2 (Apr. 1985), 74--123.

....of #( K L ) contains # 1 (q) or, equivalently, which triangle of #(#( K L ) contains q. This is a standard point location problem in an irregular triangulation. We use the point location algorithm of Brown and Faigle [2] which avoids looping that can occur with non Delaunay meshes [10, 9]. Once we have found the triangle i j, k which contains q, we can write q as q = #(p i) # #(p j) # #(pk ) and thus # 1 (q) p i #p j #pk # #( K L ) Figure 10 shows the result of this procedure: a level 3 uniform remeshing of a 3 holed torus using the # 1 map. A note ....

GUIBAS, L., AND STOLFI, J. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics 4, 2 (April 1985), 74--123.

....structure for STL [19] also limited to 2 manifolds, and the data structure that ACIS modelers build and exchange in . sat files [21] Another important non manifold representation forms the basis for the Noodles system developed by Gursoz, et al. 12] Guibas and Stolfi s quad edge data structure [11] is limited to 2 manifolds but can simultaneously represent the topology of an object and its dual. 2.2 Out of Core Algorithms Numerous out of core techniques have been developed for other geometric applications. In the graphics domain, these applications include large building walk throughs, ....

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.

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

First 50 documents  Next 50

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


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