L. J. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph., 4, 1985.  Home/Search   Document Not in Database   Summary   Related Articles   Check

....where C(f 0 ) is the number of edges on the boundary of f 0 . The insertion and deletion each costs O(log 2 n) and the cost of reporting the edges on the boundary of the new face f 0 is proportional to the number of these edges [15] We keep a data structure, say a quad edge structure [11], that describes all the faces of A(V ) that have already been constructed so that we do not construct the same face twice. The cost of updating the quad edge structure with the new face is proportional to C(f 0 ) We continue exploring the faces through which fi passes by moving ....

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

....that the Delaunay triangulation D of a set X 2 IR d of n points is given by an internal representation such that constant time access between neighboring simplices (i.e. triangles for d = 2, tetrahedra for d = 3) is possible. This can be achieved by using, e.g. the 2D quad edge data structure [GS85] the edge facet structure in 3D [DL89] its specialization and compactification to the domain of 3D triangulations [E93] or its generalization to d dimensions [Bri93] Now, in order to locate a query point q, select some simplex of D, consider the line segment L from a vertex of the initial ....

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

....This trivially follows from the fact that a DT is invariant to translations of the input set of sites. The value of ff doesn t matter either since it neither affects the topology of the convex hull, nor its projection on the plane 2. 1 The Quadedge Data Structure The quadedge data structure [13] was designed for representing general subdivisions of orientable manifolds. It simultaneously represents both the subdivision and its dual. Alternatives are the double connected edge list (DCEL) 24] and the winged edge data structures, which do not hold the dual. The quadedge structure has been ....

....the subdivision is a triangulation, it is possible to simplify some of the operations: e:Dprev = e:Onext:Rot 2 :Onext e:Dnext = e:Rot:Onext 2 :Rot (2.5) The next section presents higher level operators. 2. 2 Topological Operators Starting with the operator set proposed by Guibas and Stolfi [13], we have modified it to make it more symmetrical, and also to eliminate superfluous edge navigation. The parameters of the Connect operator have been changed and its inverse operator Disconnect is introduced. The latter accommodates some operations that were previously part of DeleteEdge. As a ....

[Article contains additional citation context not shown here]

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.

....or an edge into the subdivision. While edge insertion is uniquely defined, vertex insertion can be performed either by creating an isolated vertex, or by inserting a vertex along an existing edge, which is split into two edges. The dual operations of edge insertion and deletion are also useful [76]: an expansion splits a vertex v into two new vertices connected by an edge; each new vertex inherits a subsequence of the edges formerly incident on v. A contraction merges two adjacent vertices v 1 and v 2 into a new vertex, which inherits the edges incident on both v 1 and v 2 . 6.1 Dynamic ....

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

.... distance we shall call them d circles) After this, in some sense, negative result, we are interested in knowing when this procedure of reduction permits to obtain, if not the exact diagrams, at least their topological shape, as this is the hardest part in the computation of a Voronoi diagram ([4]) We find the next negative result, with the additional hypothesis of the distances being smooth (i.e. with smooth circles) Theorem 2. Let d and ffi be two strictly convex and smooth distances in the plane. If there exists a bijection f from the plane onto itself such that for every finite set ....

Guibas, L. and Stolfi, J., "Primitives for the manipulation of General Subdivisions and the Computation of Voronoi Diagrams", ACM Transactions on Graphics, Vol. 4, N o 2, 74-123. April 1985.

....with adjacencies to neighboring cells. The boundary representation, for short b rep, describes a 3 dimensional model through its boundary complex, which consists of vertices, edges, and 2dimensional faces. The winged edge structure of Baumgart [4] and the quad edge structure of Guibas and Stolfi [51] are examples of b rep data structures that assume the boundary is a manifold. This means every point of the boundary has a local neighborhood homeomorphic to R 2 . If the boundary is triangulated then every edge belongs to two triangles and every vertex belongs to a simple cycle of triangles ....

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

....map, and in computational geometry as an arrangement in the plane [6] Data structures describing embeddings of planar graphs in the plane can be traced back to Baumgart s winged edge data structure and have been Research Report No. 1 May 2 Michel Gangnet et al. studied by numerous researchers [20, 12, 7]. It is standard practice to distinguish between the geometry, that is the position of the vertices and the geometric definition of the edges, and the topology, that is the incidence and adjacency of the vertices, edges, and faces. The problem addressed here is building a data structure to support ....

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

....representation of the Voronoi diagram V (S) of S that consists of a topological component and of a geometric component. The topological component of V (S) is the planar embedding of V (S) represented by a suitable data structure (e.g. doubly connected edge lists [22] or the data structure of [15]) The geometric component of V (S) stores the following geometric information for each vertex and edge of the embedding: ffl For each vertex v of V (S) V (S) stores semiintegers x (v) and y (v) that approximate the x and y coordinates y(v) of v, We provide the definition of y ....

....has the same asymptotic time complexity as a point location query in the corresponding explicit Voronoi diagram. In order to compute the implicit Voronoi diagram V (S) we begin by constructing the Delaunay triangulation of S, denoted DT (S) by means of the O(n log n) time algorithm of [15], which has degree 4 because its most expensive operation in terms of the degree is the incircle test (see Lemma 3) The topological structure of V (S) and the sites (e) and r(e) for each edge e of V (S) are immediately derived from DT (S) by duality. Next, we compute the approximations x ....

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.

....for example, by using the basic algorithm Generate Random Nodes or by manual node creation using the Edit Graph feature of the instance menu. The Delaunay triangulation 4 of the nodes is computed and the triangulated graph is displayed. Here, the algorithm of Guibas and Stolfi is implemented [GS85] 4 See Section 1.4 for the definition. Figure 4.12: A solution of the Three Terminal Vertex Disjoint Menger Problem. A maximum set of 6 paths between nodes f30; 17; 18g have been determined. In black and white mode, the paths belonging to the solution are dashed. Figure 4.13: A solution of ....

....classes: LEDA UGRAPH: LEDA graph class for undirected graphs. quad graph: Planar graph class. The graphs in the problem class enforce a fixed embedding in the plane. See also Appendix G.7 for a more detailed description and an example. The graph class is a slightly modified implementation of [GS85] By the methods described there the insertion and deletion of an edge take O(1) time. For each edge, the adjacent nodes and faces can be determined. Furthermore, for each node, the edges are ordered around the node according to their embedding. For each insertion or deletion, the face ....

[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:75--123, 1985.

....in order to process various types of map input. 3 The One Step Algorithm Further consideration led to the examination of the relationship between Voronoi edges and Delaunay edges in the original Voronoi Delaunay construction. This was made simpler by the use of the Quad Edge data structure [GS85], where two of the pointers refer to Delaunay vertices, and two to the dual Voronoi vertices. Our intuition was to apply the crust test to individual QuadEdges on the original diagram, rather than creating a second structure. The circle in Figure 7 above, for example, contains a crust edge but no ....

....Figure 7 above, for example, contains a crust edge but no skeleton edges. Thus, for each Quad Edge, we wished to determine if the Delaunay edge had a circle that was empty of Voronoi vertices (and hence of a portion of the skeleton) and which intersected the Delaunay edge. In the terminology of [GS85], if Q.Vertex was a Delaunay vertex, we constructed a circle using Q.Vertex, Q.Rot.Vertex and Q.Sym.Vertex. If this circle was valid, then we tested if Q.Sym.Rot.Vertex fell Figure 11: One step crust and skeleton. Figure 12: Enlargement of part of Figure 11. outside the circle. In this case the ....

[Article contains additional citation context not shown here]

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

....between cells. For example, there is a natural order among the edges that appear along the boundary of a face in a planar arrangement. This leads to the cell tuple structure [Bri93] which is a generalization to any dimension of the two dimensional quad edge structure of Guibas and Stolfi [GS85] and the three dimensional facet edge structure of Dobkin and Laszlo [DL89] The cell tuple structure gives a simple and uniform representation of the incidence and ordering information in the arrangement. SKELETON Let H be a finite set of hyperplanes in R d . A skeleton in the arrangement ....

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.

....to construct the Delaunay triangulation in the plane was published in 1980 by Lee and Schachter ( 8] Their method which will be referred to in the text as the standard algorithm was based on the famous divide and conquer paradigm. In 1985, Guibas and Stolfi generalized this method ([6]) Meanwhile, in 1984, A. Maus ( 9] published the first expected linear time method for constructing the Delaunay triangulation of a site of planar points, using a grid to speed up the location of the closest empty circle neighbour for any given Delaunay edge. In 1987, R. Dwyer published an O(n ....

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

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

....the edges of the image, significant errors are introduced if the calibration near the edges is extrapolated from points in the interior of the image. 6.2 Triangulation We then construct a constrained Delaunay triangulation, using the ellipse centers as vertices. We use an incremental algorithm [5, 6], which must be given a polygonal region R of the plane to triangulate. If extrapolation to the extreme edges of the image is required, R should be the outer boundary of the image. However, the calibration function is significantly less accurate when extrapolation is required. Therefore, for the ....

Guibas, Leonidas and Jorge Stolfi (1985) "Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams," ACM Tran. on Graph. 4/2, pp. 74--123.

.... only source of curvature in a piecewise linear surface, this implies that a BTM is flat the neighborhood of any point looks like a portion of the Euclidean plane [28, 41] One can represent a BTM, or any other 2 d simplicial complex, in a computer using Guibas and Stolfi s quad edge structure [25], Baumgart s winged edge structure [4] or the dual graph of the simplicial complex. In our algorithms, we require that each triangle of M be able to access its incident edges and each edge of M its incident triangles in constant time. If a polygonal region R is given, we can triangulate R and ....

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.

....scale analyses. As problem sizes become this large, efficient mesh generation becomes a critical component both for sequential and parallel execution of large solvers. There exist many sequential algorithms for constructing Delaunay triangulation. For example, sweep line [5] divide and conquer [6, 8] and point insertion [4] just to name a few. Work on parallelization of mesh generation has also been reported in literature [3, 9, 10] In this paper, we aim to study the parallelization of Delaunay triangulation with High Performance Fortran. In particular, we would like to investigate the ....

....be easily modified to compute the DT directly. ffl Divide and conquer (D C) This method recursively partitions and constructs local triangulation of the point set, and then the DT is obtained by merging all the triangulations. Details of this method is described in Section 3.1. These algorithms [6, 8] gave an O(n log n) DT which is asymptotically optimal. Parallelizing Mesh Generation Code with HPF 3 2.2 Domain decomposition algorithm In the domain decomposition approach, there are two possible strategies for constructing DT, as shown in Figure 1: 1. Grid the interface first, and then grid ....

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

....convex faces. In the event that the input subdivision has nonconvex faces, we first convexify (e.g. by triangulation) We will assume that S is given to us in a convenient data structure that allows the usual basic operations to be done in constant time; e.g. the quad edge data structure [7] is one possibility (a variant of which is used by our code) Let n denote the total number of vertices of S. Then S also has O(n) faces and edges. Each face f has an associated integer weight ff f 2 f0; 1; W; 1g. The weight of an edge e is also an integer ff e 2 f0; 1; W; 1g and ....

....is lessened by measuring the time performance for the each algorithms measured on the CPU clock and by counting the number of elementary operations performed by each algorithm during a shortest path search. Subdivision. The natural choice for representing the input subdivisions is the quad edge [7] data structure. Because of the limited operations needed, and the fact that the datasets are terrains, the implementation is simplified: Rot (edgedual) and Flip (orientation) are not implemented. Faces and vertices of the planar subdivision are objects with attributes. The vertices have (x; ....

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.

....test data. Figure 8: A mesh for a front view of the CT pelvis data, generated from iso contours with constrained Delaunay triangulation. be producedby first meshing the iso contour grid into triangles, then rendering the triangles by interpolating the vertex values. We use Delaunay triangulation [6] to create the triangle mesh from the set of points defining the contours. Thesegmentsalong the contours are constrained to be edges of triangles, which guarantees that no triangle will cross an iso contour. This constraint method was used earlier by Lischinski et al. 10] in connection with ....

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.

....Euler s formula for planar graphs, Observation 2.9 gives an optimal representation for 3 D convex hulls since the size of the data structure can be made linear in the number of interesting features (vertices, arcs, and curved or planar facets) of the hull using standard representations . MP78, GS85] 3 Generalized IH We defined f IH in a previous report and showed that to compute the convex hull of a set A, one may find all the bounding and supporting hyperplanes of A, compute their f IH, and repeat these two steps on the resulting set again (see also Appendix A) Though the computation ....

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.

.... by Preparata end Shamos [Pre85] the winged edge by Baumgart [Bau75] the half edge structure by Mantyla [Man88] the vertex edge and face edge structures by Weiler [Wei85] and, in a generic dimension d, the cell tuple structure [Bri93] and the generalized maps [Lie91] The quad edge structure [Gui85] can be viewed as a specialization of the cell tuple structure in two dimensions (see Chapter 2 for a treatment of data structures for planar subdivisions) Some special structures have been developed in the literature for triangulations and trapezoidal decompositions, which can exploit nice ....

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

....of the Voronoi diagram. In contrast with DT (S) DT (S 0 ) has the nice property that there are exactly d 1 (d 1) tuples adjacent to each (d 1) tuple in DT (S 0 ) This will significantly simplify the description of the algorithm presented below. Next, we adopt two functions 1 from [GuSt 85] providing a nice classification of the (d 1) tuples of the extended Delaunay graph DT (S 0 ) In particular, let v(P 0 ; P d ) denote the center of the hyperball C(P 0 ; P d ) of d 1 sites P 0 ; P d 2 S, we have: fP 0 ; P d g 2 DT (S 0 ) v(P 0 ; ....

L. Guibas and J. 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

....and, less obviously but equally importantly, how to orient the elements of the fiber product defining the convolution so that together they form another tracing manifold. We describe a data structure for representing polyhedral tracings based on the quad edge data structure of Guibas and Stolfi [10] and give an efficient algorithm for computing the convolution of such tracings. Given tracings B and R of size m and n respectively, their convolution Q = B R can have size Theta(mn) in the worst case. If the actual size of Q is k, then we can compute Q in output sensitive time O(kff(k) log 3 ....

....using a sound set of conventions. A polyhedral tracing is a tracing such that its domain manifold can be decomposed into (interior disjoint) simply connected subsets of three types: vertex domains, edge domains, and face domains, with connectivity properties akin to a subdivision as defined in [10], and such that (Figure 1) 1. On a face domain, the whisker map is constant and the location map is a bijection whose range is a simple planar polygon, 2. On an edge domain, the location map range is a line segment (corresponding to a shared edge between the polygonal ranges of the two adjacent ....

[Article contains additional citation context not shown here]

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.

No context found.

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

No context found.

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

No context found.

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

Documents 151 to 200  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