Guibas, Leonidas, & Stolfi, Jorge. (1985). Primitives for the manipulation of general subdivisions and computation of Voronoi diagrams. ACM transactions on graphics, 4(2), 74--123.  Home/Search   Document Not in Database   Summary   Related Articles   Check

....love referential transparency the ability to substitute equals for equals which is why assignments are frowned upon. Unfortunately, assignments are indispensable for many data structures including simple ones like doubly linked lists and complex ones like the quad edge data structure (Guibas Stolfi, 1985). Not using assignments, however, has its merits: purely functional data structures are automatically persistent. A data structure is called persistent if, after an update, the old version of the data structure is still available for processing. By contrast, imperative data structures are ....

Guibas, Leonidas, & Stolfi, Jorge. (1985). Primitives for the manipulation of general subdivisions and computation of Voronoi diagrams. ACM transactions on graphics, 4(2), 74--123.

....domain, and (d) curved domain. without specifying the exact form of this representation. Computational geometers typically assume exact, combinatorial data structures, such as linked lists for simple polygons and polygons with holes, doubly connected edge lists [103] or quad edge structures [63] for planar multiple domains, and winged edge structures [44, 62] for polyhedral domains. In practice, complicated domains are designed on computer aided design (CAD) systems. These systems use surface representations designed for visual rendering, and then translate the final design to another ....

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

....we use is abstractly similar to their adaptive precision, but the engineering and resulting performance are quite different. 2 Experimental results We experimented with three implementations of Delaunay triangulation algorithms, the 2 d flipping algorithm [11] the 2 d divide and conquer algorithm[7, 15], and a random incremental convex hull algorithm [4] used to compute Delaunay triangulations via the lifting map[7] The last implementation handles general dimension, but we used it only for threedimensional Delaunay triangulations, corresponding to four dimensional convex hulls. All programs are ....

.... 2 Experimental results We experimented with three implementations of Delaunay triangulation algorithms, the 2 d flipping algorithm [11] the 2 d divide and conquer algorithm[7, 15] and a random incremental convex hull algorithm [4] used to compute Delaunay triangulations via the lifting map[7]. The last implementation handles general dimension, but we used it only for threedimensional Delaunay triangulations, corresponding to four dimensional convex hulls. All programs are written in the C language. All the algorithms require the orientation test and the incircle test. The orientation ....

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.

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

....of Amenta, Bern and Eppstein [ABE98] and modify it to extract the skeleton from unlabelled vertices. We find that by reducing the algorithm to a local test on the original Voronoi diagram we may extract both a crust and a skeleton simultaneously, using a variant of the Quad Edge structure of [GS85]. We show that this crust has the properties of the original, and that the resulting skeleton has many practical uses. We illustrate the usefulness of the combined diagram with various cartographic applications. 1 Introduction and Previous Work Workers in both Computational Geometry and ....

....The Voronoi diagram is implemented using the Quad Edge structure and an incremental Voronoi Figure 4: Extracted arcs. Figure 3: Voronoi Delaunay tessellation. Figure 2: Fringe points. Figure 1: A forest map. Figure 5: Topologically complete map. algorithm that closely follows that given in [GS85] among others. In the rapid digitizing procedure of [GNY96] the operator digitizes the interior of each polygon, inserting points around the perimeter, each with the polygon label. The Delaunay triangulation Voronoi diagram is then constructed, and the triangulation is traversed once, using 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.

....are represented using a winged edge data structure and a preprocessing step is performed to detect touching objects, which is a necessary step for the treatment of degeneracies. The hierarchical triangulation has been incorporated into the same system. We use the public domain implementation of [GS85] by Dani Lischinski [Lis94] for the constrained Delaunay triangulation. Each subdivided polygon contains a triangulation QuadMesh. On our test scenes, the algorithm spends most of its time on the visibility update, especially the calculation of the views at new vertices for the receiver ....

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

....triangulations for constructing the approximate surface. Delaunay triangulation is a purely twodimensional method; it uses only the xy projections of the input points. It finds a triangulation that maximizes the minimum angle of all triangles, among all triangulations of a given point set [12, 20]. This helps to minimize the occurrence of very thin sliver triangles. Data dependent triangulation, in contrast, uses the heights of points in addition to their x and y coordinates [7, 26] It can achieve lower error approximations than Delaunay triangulation, but it generates more slivers. The ....

....approximations than Delaunay triangulation, but it generates more slivers. The incremental Delaunay triangulation algorithm starts with a simple, initial triangulation and inserts the points as vertices in the triangulation one by one, performing local topological updates after each insertion [12, 20]. The procedure to insert a single vertex is illustrated in Figure 1, and works as follows: To insert a vertex A, locate its containing triangle, or, if it lies on an edge, delete that edge and find its containing quadrilateral. Add spoke edges from A to the vertices of this containing polygon. ....

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

....based on the coordinates and the mark of a point. By convention, the user marks the uninterested edges with 0. The mesh generation is designed using the object oriented technology. We separate the mesh representation from the algorithms. Internally, the Mesh class uses the eOEcient quad edge [8] data structure to represent the mesh. The algorithms, including Delaunay triangulation, Delaunay re nement, and adaptive re nement, are designed using the high level interfaces of the Mesh class. Each algorithm is encapsulated in a separate class. The current mesh generator in SIFFEA is ....

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

....edges, and faces. Connected components of embedded planar graphs can be represented in the computer by data structures, such as the winged edge [5] that store these topological relationships. In our opinion, the most elegant of the topological data structures is the quad edge of Guibas and Stolfi [17], which simultaneously represents both primal and dual (e.g. both the Voronoi and Delaunay) in a symmetric manner. We use the quad edge data structure to store the topology of the original network, including lakes and double line rivers. By computing the medial axes of these polygonal features, ....

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.

....to increase efficiency; the memoization associated with lazy evaluation is a good example. However, these effects are only benign in the sequential case; in the parallel case synchronization overhead can mitigate or even negate, the efficiency gains of using these techniques. the literature [13, 4, 8, 7], but all use ephemeral data structures. We present a new incremental algorithm to compute the 3d convex hull of a set of points (and by reduction a 2d Delaunay triangulation) based on a fully persistent representation of its hull, which is a triangulated surface. By using the persistent ....

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.

....we include it in Figure 3. The function wall( recognizes selected edges by examining the coordinates of three consecutive vertices in counter clockwise order. drawTraverse( implements the traversal without making changes to the data structure. These are based on a quadedge like data structure [11] that uses directed edges: Sym(e) reverses edge e, and Lnx(e) and Lpr(e) give the ccw and cw edges around the face to the left of e. boolean wall(int e) return p(e) greatereq(p(Lnx(e) p(Lnx(e) greater(p(Lnx(Lnx(e) boolean entered(int e) return p(e) greatereq(p(Lpr(e) ....

....graph in which every face has a traversable triangulation. Figure 2 actually showed a traversable triangulation of Figure 5. Only if one chain of each face is a single point is the traversable triangulation unique. We can build traversable triangulations with a standard incremental construction [11] if we carefully consider diagonal swaps for quadrilaterals with co circular vertices. Lemma 5 An incremental algorithm builds a traversable triangulation for a set of points S. After point location, insertion of a point p takes time proportional to its degree. Proof : For this abstract, we ....

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

....by a logarithmic factor. Furthermore, we believe that our method is simpler: whereas they use an advanced data structure (the data structure of Overmars and van Leeuwen [17] for dynamic convex hulls) our method only uses fairly standard data structures (red black trees, and a quad edge structure [14] for representing planar subdivisions) Our second result, presented in Section 3, concerns the discrepancy of planar point sets with respect to the family of all possible strips. A strip is the area enclosed by two parallel lines. We show that the strip discrepancy can be computed in O(n 2 2 ....

....pq in the arrangement A(S ) defined by the lines in S . Hence, in the dual setting our problem becomes the following: given a set S of n lines, compute the level of each vertex in the arrangement A(S ) A convenient representation of an arrangement of lines is the quad edge structure [14]. This structure allows us to traverse the arrangement in a systematic way: we can visit all the edges that bound a given cell, we can step from one cell to the cell that shares a given edge with it, and so on. A quad edge structure for an arrangement of n lines can be constructed in O(n 2 ) ....

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.

....graph of the extended Delaunay graph DT (S 0 ) the topological structure 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 ) The following two functions, adopted from [19], provide a nice classification of the (d 1) tuples of the extended Delaunay graph DT (S 0 ) In particular, let VOL and INS (mnemonic for volume and insphere ) be defined as follows: VOL(P 0 ; P d ) fi fi fi fi fi fi fi 1 P 01 : P 0d . 1 P d1 : P dd ....

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

....between 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. If we perform both halving steps for the halfedge data structure, we end up with the quad edge data structure [11]. It provides a fully symmetric view on the primal and the dual graph, as can be seen in Figure 5. Instead of using opposite pointers, a two bit counter r is used to address a slot in an edge record of four quad edges. With an additional bit f per edge for the flipped status the quad edge data ....

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

....present our algorithms using the doubly connected edge list structure [4, 14, 17] a standard data structure used in computational geometry that stores topology explicitly. This is not a restriction; simple adaptations to the algorithms can be done so that they apply to the quad edge structure [13], the fully topological network structure [3] the ARC INFO structure [15] the DIME file [16] or any other vector data structure that stores the topology explicitly. In the next section we give a brief description of the doubly connected edge list structure. Then we proceed with the simple ....

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.

....may represent city blocks, parcels, and buildings in different levels to improve data structure organization. Thus, many important applications require not only explicit topological information, but also support for hierarchies. It is possible to use a conventional topological data structure [4, 5, 6] to represent a hierarchy of planar subdivisions. However, it is conceptually cleaner to use data structures that directly support hierarchical relationships; it is also much easier to maintain global consistency. In this paper, we present HPS, a new topological data structure with built in ....

....two faces and two vertices. Thus, it is natural to base representations for planar subdivisions on edge adjacencies. The first edge based data structure was the winged edge data structure [8] Many other data structures have been proposed since then (e.g. half edge [4] face edge [5] quad edge [6]) but they are all variations of the winged edge. Of interest here are variants that explicitly support orientation and faces with holes. Besides vertices, edges, and faces, these variants explicitly represent loops and edge uses. Loops provide a representation for faces with holes. Each face has ....

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.

....that the Delaunay triangulation D of a set X 2 IR d of n points is given by an internal representation such that constanttime 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. Transactions on Graphics, 4(2):74-- 123, 1985.

....such models, it is advisable to handle separately its topological properties (the contacts between faces, edges, and vertices) from its geometrical properties (vertex coordinates, face equations, etc. This separation greatly improves the modularity and versatility of geometric algorithms [12,18]. A two dimensional cellular complex is a mathematical structure that captures the topological aspects of such a boundary model, freed from all geometrical data. Informally, it consists of one or more polygons, whose sides are conceptually identified in pairs, in a specified direction. The pairing ....

....is a purely combinatorial data structure that describes the incidence relationships between the faces, edges and vertices of the complex. In the literature one can find dozens of data structures that were developed for this purpose [6,9,18,25] For our work we selected the quad edge data structure [12], a variant of the winged edge and half edge structures [2] which are widely used in CAD and computer graphics. The main reason for this choice was that the quad edge allows the encoding of non orientable cellular complexes, such as the one of figure 1; as well as degree 1 vertices, loops, ....

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

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