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

....A graph is planar if it can be drawn in the plane such that no two edge cross (except at their endpoints) Such a drawing is called an embedding of the planar graph. We represent embeddings by assigning to each vertex v a cyclic ordering of the edges leaving v, as defined by Guibas and Stolfi in [24]. For each edge e = u; v) of the planar graph G, define two directed versions of e: one going from u to v, and another (symmetric) going from v to u. Denote a directed edge by putting an arrow on it: e . For each directed edge e denote its left and right faces Lef t( e ) and Right( e ) ....

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

....correct, since 2 D viewing is the main application. Those models are not guaranteed to be complete or to correspond to a proper polyhedron [9] since they lack topological information. Our planner uses solid models having a Polyhedral Boundary Representation (i.e. Quad Edge Data Structure [6]) So we need to be able to transform these existing graphics based models to a solid, watertight boundary representation (i.e. no dangling faces) A common problem is that models are not watertight. Often, parts of the boundary are missing and the object is not bounded or closed. Also, the ....

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

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

....just as rarely used in practice. 3.1 Computational Geometry It is well known that computing the sign of a determinant is a fundamental primitive operation in geometric algorithms. Thus algorithms for convex hulls, Voronoi diagrams, Delaunay triangulation can be reduced to this operation (e.g. [44]) More generally, problems related to computing the arrangement (or subparts thereof) of a set of hyperplanes can all be reduced such primitives. We note that Clarkson [22] has shown that the sign of a determinant can be computed more efficiently than evaluating the determinant: using ideas from ....

....but this has no counterpart in f.p. computation, so the effects of growing input number lengths cannot be compared. Karasick, Lieber and Nackman. These authors described in [55] their experience in implementing the Guibas Stolfi algorithm for Delaunay triangulation for a set of planar points [44]. The input points have coordinates that are rational numbers, and in the course of the algorithm they must determine the signs of n Theta n determinants where n 4. Assuming the rational numbers have 3 digits in the numerator and denominator (a digit is 16 bits here) their initial ....

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.

....returns a pointer to the edge (v; u) See Figure 1 for an illustration of these functions. This functionality is available in or can be simulated by the most commonly used data structures for storing planar subdivisions including the doublyconnected edge list [11, 14] the quad edge structure [8], the fully topological network structure [1] the ARC INFO structure [12] and the DIME le [13] Our algorithm also requires the use of some geometric operations. Let dist(a; b) be the distance between two points a and b. Let ab be the direction of the ray originating at a and containing ....

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

.... the largest circumscribed circle [D AS89] the largest minimum enclosing circle [D AS89, Raja91] and the integral of the gradient squares [Ripp90] Algorithms that construct the Delaunay triangulation of a given set of n points in the plane in time O(n log n) can be found in Guibas, Stolfi [GuSt85], Fortune [Fort87] Guibas et al. GKS90] and other publications in computational geometry [PrSh85, Edel87] In practical applications it is often the case that a constraining set of points and line segments must be part of the triangulation. The constraining set is most naturally modeled as a ....

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. An Upper Bound for Conforming Delaunay Triangulations 15

....Sun Yat Sen University, Kaohsiung, Taiwan, March 2000. 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 [7] divide and conquer [8, 10], incremental construction [6, 3] and point insertion [5] just to name a few. Work on parallelization of mesh generation has also been reported in literature [4, 11, 12] In this paper, we aim to study the parallelization of Delaunay triangulation with High Performance Fortran. In particular, we ....

.... conquer, and incremental construction. Divide and Conquer (D C) This method recursively partitions and constructs the local triangulations of the point set, and then the DT is obtained by merging all the triangulations. Details of this method are described in Section 3.1. These algorithms [8, 10] gave an O(n log n) DT which is asymptotically optimal; Incremental Construction (I C) With an initial Delaunay triangle, the generic DT can be constructed by successively building simplices next to the previous simplex, and the circumcircles of new simplices contain no point in P . The details ....

[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 Transaction on Graphics, 4 (1985), pp. 74--123.

....a set L of e n chains with a corresponding set S of n edges. Let K L be a subset of chains of L and let R S be the corresponding set of edges. For convenience, we write T (K) to denote the trapezoidation T (R) We suppose that we are given a planar subdivision representation (e.g. see [3, 19, 26]) of T (K) This planar subdivision has O(jRj) faces and each face has at most 2 edges and 4 vertical rays on its boundary. For our application, we need a planar subdivision with O(jKj) faces, each of which is conformal [4] that is, bounded by portions of at most (a) b) Figure 5: a) ....

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

.... smallest enclosing circle [D AS89, Raj91] and the minimum integral of the gradient squared [Rip90] Efficient algorithms for constructing Delaunay triangulations are abundant in the literature and based on such diverse algorithmic paradigms as edge flipping [Laws72, Laws77] divide andconquer [ShHo75, GuSt85], geometric transformation [Brow79] plane sweep [For87] and randomized incrementation [GuKS90] Recently, polynomial time algorithms have also been found for the minmax angle and the minmax edge length criteria [EdTW92, EdTa91] The method of [EdTW92] is most relevant to this paper. It ....

....maximizes the increasing vector of triangle measures can be constructed in the same amount of time and storage. Proof. To achieve the claimed bounds, the above algorithm uses two data structures taking a total of O(n 2 ) storage. First, the quad edge data structure of Guibas and Stolfi [GuSt85] stores the triangulation in O(n) memory and admits common operations, such as removing an edge, adding an edge, and walking from one edge to the next in constant time each. The other data structure is the bit array mentioned above. The quad edge data structure together with the ear cutting method ....

[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. Graphics 4 (1985), 74--123.

....position, i.e. a face of P and a face of C may intersect only if the sum of their affine hulls is the entire space. The intersection of two regular polyhedra in general position is again regular. The standard data structures for three dimensional polyhedra, e.g. the quad edge structure of [GS85, EM85], the doubly connected edge list of [MP78, PS85] and the half edge structure of [Man88] cannot represent all polyhedra. This implies that the class of representable (in any one of these data structures) polyhedra is not closed under the basic boolean operations intersection, union, and ....

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.

....Structures. Data structures are ways to organize data in a computer. Common examples of data structures are arrays, stacks, priority queues, and trees. These are wellknown and discussed in many standard texts on algorithms; see, for example, CLR90] We next introduce the quad edge data structure [GuSt85] to store a plane geometric graph G. Loosely speaking, it stores each edge of G four times, twice for its two incident faces and twice for its two endpoints 3 . Figure 1.2 shows an example of the quad edge structure for a plane geometric graph that bounds polygonal regions A and B. Strictly ....

....been a prominent subject in the study of triangulations; it is related to many positive results known in the area. Besides the O(n 2 ) time edge flip method (Section 2. 3) Delaunay triangulation can be computed in Theta(n log n) time by diverse algorithmic paradigms such as divide and conquer [GuSt85, ShHo75], geometric transformation [Brow79] and plane sweep [Fort87] Furthermore, it can be computed in time O(n log n) with high probability by randomized incrementation [GKS92] Among all triangulations of a given point set S, the Delaunay triangulation optimizes criteria such as the max min angle ....

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.

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

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.

No context found.

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

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