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  Home/Search   Document Not in Database   Summary   Related Articles   Check

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

....closest point problems in higher dimensions [Ben80] Bentley uses this data structure in the plane to answer fixed radius nearest neighbor queries in his traveling salesman programs [Ben89] Constructing planar Voronoi diagrams has also received a large amount of attention. Guibas and Stolfi [GS85] present a unified framework and ideal data structure for computing and representing the diagram and its dual. Their algorithms then construct Delaunay triangulations rather than Voronoi diagrams. We also will use this approach because the resulting algorithms are simpler and more elegant. Guibas ....

....outlines areas of future work. Chapter 2 Practical Sequential Voronoi Algorithms Every man is the center of a circle, whose fatal circumference he cannot pass. John James Ingalls Sequential algorithms for constructing the Voronoi diagram come in three basic flavors: divideand conquer [Dwy87, GS85] sweepline [For87] and incremental [CS89, GS77, Mau84, OIM84] This chapter presents an experimental comparison of these algorithms. In addition, it describes a new incremental algorithm that is simple to understand and implement, but still competitive with the other, more sophisticated methods ....

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

.... systematic the very simple flip algorithm (repeatedly apply the flip rule) will converge to the Delaunay triangulation, so the Delaunay triangulation maximizes the minimum angle over all triangulations it is a globally optimized triangulation (GOT) Because DT is local, the incremental algorithm [15, 11] will make at most O(n) changes to the triangulation when adding a new site, giving a worst case of O(n 2 ) time to compute the Delaunay triangulation. Guibas, Knuth and Sharir [10] show that the average 3 number of sites adjacent to a new site is O(1) so the incremental algorithm will make ....

....the edge of D 0 E 0 G and F 2 Q Gamma (ABC) Q Gamma (D 0 E 0 G) by theorem 1) we can find an F 0 2 D 0 E 0 G Q Gamma (D 0 E 0 G) which contradicts Q being a flip rule. 2 2. 2 Circumscribing rules are systematic and local The proof that DT is systematic and local [11] relies on the following geometric fact: If two circles share a common chord, then on each side of the chord the interior of one circle is a subset of the interior of the other circle. If Q is circumscribing then the same fact is true, provided we replace circle with curve from Q 0 . ....

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

....National Science Foundation under Grant ASC 9318163. right of, or on a line or plane; it is an important predicate used in many (perhaps most) geometric algorithms. The incircle test determines whether a point lies inside, outside, or on a circle or sphere, and is used for Delaunay triangulation [8]. Inexact versions of these tests are vulnerable to roundoff error, and the wrong answers they produce can cause geometric algorithms to hang, crash, or produce incorrect output. Although exact arithmetic banishes these difficulties, it is common to hear reports of implementations being slowed by ....

....enough. 5.4 Triangulation To evaluate the effectiveness of the adaptive tests in applications, I tested them in two of my Delaunay triangulation codes. Triangle [14] is a 2D Delaunay triangulator and mesh generator, publicly available from Netlib, that uses a divideand conquer algorithm [11, 8]. Pyramid is a 3D Delaunay tetrahedralizer that uses an incremental algorithm [15] For both 2D and 3D, three types of inputs were tested: uniform random points, points lying (approximately) on the boundary of a circle or sphere, and a square or cubic grid of lattice points, tilted so as not to be ....

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.

....metric, expressed in terms on the number of case segments n, are given herein. Exploiting Geometry in Analogical Route Planning JETAI 12 Conforming Delaunay Triangulation. The Delaunay triangulation of the vertices of the case graph can be formed in O(n log n) time (Lee Schachter 1980; Guibas Stolfi 1985). The number of additional vertices added to split segments to form a conforming Delaunay triangulation is small in practice 1 . Edge Costs. Because the triangulation is planar, the number of edges E in the triangulation is O(n) The average number of edges in the diametral circle of an edge is ....

....Planning JETAI 15 reflect the evaluation. Since fi captures situational information, and may vary with the identity of the user, the metric will become biased towards routes that the user prefers in specific conditions. Vertices can be added incrementally to a Delaunay triangulation (Lawson 1977; Guibas Stolfi 1985), so it is possible for the case library to grow without any need to retriangulate the entire graph. Inserting a new vertex is a two step process: i) delete any triangles whose circumcircles contain the new vertex (Figure 14a) ii) add edges to connect the new vertex to its surrounding vertices ....

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.

.... decompostion In this section, we sketch an algorithm to compute the notch cutting decomposition in O(nr log r r 3 ) time and space, which improves on the algorithms of Chazelle [5] and Dey [9] We assume that the surface of the original polyhedron P is stored in a winged edge [1] quadedge [14], or equivalent data structure. That is, that vertices and faces can access their incident edges (and vice versa) in sorted order. We produce quadedge structures for each convex piece in the final decomposition. Theorem 3.6 One can compute the notch cutting decomposition of a polyhedron P with n ....

Leonidas Guibas and Jorge Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph., 4(2):74--123, 1985.

....the same vertices. We assume that G is represented so that the adjacencies for any vertex v are stored in cyclic order around v in a circular doubly linked list. For example, G could be represented using the winged edge structure of Baumgart [4] the quad edge structure of Guibas and Stolfi [29], or the doubly connected edge list structure of Muller and Preparata [40, 41] In this section we present our linear time method for constructing an O( p n) separator decomposition of G. 2.1 Our Approach Before we give our method, however, let us review the approach taken by Lipton and ....

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

....planar graph, i.e. a planar graph with the additional information on the ordering of the edges around the vertices, as given by a planar embedding. There exist several topological representations for an embedded planar graph, e.g. the DCEL representation [20] the quad edge representation [9], the dynamic representation described in [22] etc. The interface mechanism allows the implementation of multiple representations for an embedded planar graph. The users of GeomLib can select the most appropriate one by instantiating an object of the corresponding class. They can also implement ....

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.

....from the same viewpoint. We get those meshes from the original data using the following procedure. First, we label the images as background and foreground pixels based on known background color. Treating each pixel with valid foreground data point as a vertex, we perform a Delaunay triangulation [Guibas Stolfi 85] Triangles containing background pixels are removed, along with triangles that span step edges, i.e. connect an occluding surface with the occluded one. To detect step edges, we use a heuristic that takes into account both triangle edge length and triangle orientation. Finally, we organize the ....

....in Fig. 5 9(a) We place vertices corresponding to each of the viewing directions of the input images on a unit sphere, and then compute a Delaunay triangulation of the sphere using those vertices. We use an incremental Delaunay triangulation algorithm and the data structures proposed by Guibas and Stolfi [1985]. That algorithm was designed for triangulating vertices that lie in a plane; some modifications were required to perform the triangulation on a sphere. When we start rendering a frame we determine the viewing direction of the viewer and place a corresponding vertex on the unit sphere as shown in ....

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.

....again, numerical imprecision will rarely allow to check this property. One last example of the same kind is given by the following problem: Prove that N ( 4) given points are on the same circle. It is always possible to state the problem of cocircularity for four points in terms of a determinant ([13]) by observing that four points on a same circle in the plane are transformed into four coplanar points on the paraboloid of revolution Gamma : fQ(x; y; z) 2 R 3 j z = x 2 y 2 g: Repeating this process on more than four points is doomed to failure, due to imprecision. Note that the ....

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

.... This paper addresses two questions: first, what is the correct framework to use in describing a dynamic plane graph, and second, how does one implement the desired operations To describe and manipulate the dynamic plane graph, we use the subdivision representation scheme of Guibas and Stolfi [13], which we describe in more detail in Section 2. This scheme provides a pair of simple, powerful primitives from which more complicated operations such as the insertion or deletion of edges can be built. Our spanning tree algorithm is built on top of this framework. For the sake of completeness we ....

....and placing dual edges so that each one crosses only its corresponding primal 1 2 3 4 5 6 7 8 9 a b d c e f g Figure 1: A subdivision (black) and its dual (grey) edge. This embedding is called the dual subdivision S . Figure 1 gives an example of a subdivision and its dual. Guibas and Stolfi [13] propose the following notation (and corresponding data structure) for describing a subdivision S. Each undirected edge e = fu; vg of the S can be directed in two ways. If e is the directed version of e originating in u and terminating in v, then sym(e) is the version of e directed from v to u. ....

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

....order. For a better speed up one could extend the information of one edge by two pointers, which point to the next edge in clockwise order seen from V 1 and V 2, respectively. This would be similar to the winged edge data structure ( Bau83] or to its extension the quad edge data structure ( GS85] figure 2b) This will lead to a traversing speed up and to a higher memory consumption. It is also simple to get out a real half edge structure (figure 2c) from this. The only thing that has to be done is to store both directions with a pointer to each other in the described structure ....

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.

....3 Algorithms We describe the implementation details of the two arrangement algorithms. The input to either algorithm is a set of n lines. The output is a labeled combinatorial arrangement. The arrangement can be represented using for example the quad edge structure of Guibas and Stolfi [8]; we omit the routine details of maintaining the arrangement. The sweepline algorithm. Use a vertical sweepline moving from left to right. Maintain a list of the lines in vertical order and a priority queue of the x coordinates of intersections of adjacent lines. A single step is to move to the ....

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

.... upper bounds [14] Their approach was improved by Lee and Schachter who simplified the merge step by constructing the Delaunay triangulation, rather than the Voronoi diagram [10] Guibas and Stolfi further refine this approach, presenting a comprehensive description of their algorithm in one page [7]. The first O(nlogn) time and O(n) space plane sweep algorithm is by Fortune [5] He presents a geometric transformation to overcome a difficulty with adopting the plane sweep paradigm for construction of Voronoi diagrams that a Voronoi region may be encountered by the sweepline long before ....

....otherwise the InCircle test is applied and the site with the smallest circumcircle is chosen. The merge loop terminates when there are no valid sites in either D(L) or D(R) 3 Improvements: Guibas Stolfi Our implementation of the Guibas Stolfi algorithm began as the detailed description given in [7] and went through eighteen versions as we investigated various improvements. Our efforts were directed by timing tests using up to a million points sampled randomly from the unit square and detailed statistics provided by the UNIX profiler gprof. We stopped when our improvements were making little ....

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

....the link between the triangle structure and the array. The data structure used to store the three dimensional triangulation is a specialized version of the edge facet structure introduced by Dobkin and Laszlo [7] Related data structures are the quad edge structure due to Guibas and Stolfi [22], which can be used to model two dimensional manifolds, and the cell tuple structure by Brisson [2] which works in arbitrary dimensions. The edge facet structure is designed for general cell complexes in three dimensions. By reducing the scope to simplicial complexes, it is possible to improve ....

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.

....change edge weights, the most difficult operation to handle is an increase in the weight of an MST edge. However, in the dual graph this can be viewed as a decrease in the weight of a non MST edge. This idea and the handling of edge insertions and deletions are addressed by the data structures of [GuSt85] and the edge ordered tree data structure of [EpItTaTaWeYu92 ] These data structures help maintain the subdivision and its dual in the face of general updates and also help perform required access operations efficiently. Edge ordered trees are an adaptation of the dynamic trees of [SlTa83] 588 ....

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.

....of j(jK L j) contains P Gamma1 (q) or, equivalently, which triangle of P(j(jK L j) 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 fi; j; kg which contains q, we can write q as q = aP(p i ) bP(p j ) gP(p k ) and thus P Gamma1 (q) a p i b p j g p k 2 j(jK L j) Figure 10 shows the result of this procedure: a level 3 uniform remeshing of a 3 holed torus using the P Gamma1 ....

GUIBAS, L., AND STOLFI, J. Primitives for the Manipulation of General Subdivisions and the Computationof VoronoiDiagrams. ACM Transactions onGraphics 4, 2 (April 1985), 74--123.

....data structure which stores the edges incident to every vertex as a doubly linked list in the circular order in which they appear in the embedding. This structure allows also to scan the edges bounding any given face, starting from any given boundary edge. See also the quad edge data structure in [GS] for storing planar subdivisions. Once a combinatorial embedding is known, all faces can be triangulated in linear time. For such a (combinatorial) planar triangulation one could then go on to compute a straight line embedding with vertices on an (n Gamma 1) Theta (n Gamma 1) grid in linear ....

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

....of point selection is O(n log n) Procedure ADD VERTEX must take care of two tasks: 1. update the triangulation; 2. update the links between triangles and data, and the tree storing triangles. We implemented the triangulation update through an algorithm based on local edge flipping 4 proposed in [Gui85], and we added the operations for updating links after each flip operation. The algorithm first inserts point v by joining it with the vertices of the triangle t containing 4 This is a well known technique that considers a pair of adjacent triangles forming a convex quadrilateral, and swaps the ....

....edge with the opposite diagonal if the two triangles do not satisfy the Delaunay criterion. Figure 15: Steps of the refinement algorithm. v (t is known from point selection) then performs a sequence of edge flips, until the resulting triangulation is a Delaunay triangulation. It is known from [Gui85] that the number of flips at a generic refinement step i is at most O(n i ) where n i is the current number of vertices in the triangulation, yielding a total cost of O(n 2 ) in the worst case for computing the whole triangulation. Moreover, new triangles generated at each step are radially ....

[Article contains additional citation context not shown here]

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

....ff = 20 ffi . Many of the vertices along the outline were added by the algorithm. An important choice to be made in any implementation is the Delaunay triangulation algorithm to build upon. There are incremental algorithms where points are added one at a time to a growing triangulation, e.g. [10], and all at once algorithms such as the sweepline algorithm of Fortune [9] An incremental algorithm seems the logical choice, since our algorithm refines the triangulation by adding points. Though an all at once algorithm could be used for the initial triangulation, and perhaps for splitting ....

....do not report any timing measurements. We have not analyzed the asymptotic running time of the Delaunay refinement algorithm in detail. The worst case running time for incremental Delaunay triangulation is O(M 2 ) where M is the output size. In practice, such algorithms usually run much faster [10]. Much of the time is typically taken up locating the triangle containing the added point. For non input vertices, this is simplified in our algorithm by starting at the skinny triangle or encroached upon segment being split. Figure 18 shows another output of the algorithm, given as input an ....

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.

....order: 1. The swapping of the diagonals of pairs of triangles allows easily to maintain the pointtriangle relation for the points to be inserted in the refinement area. 2. For good quality triangulations the nonlinear cost of the classical Delaunay algorithm is essentially determined by step (a) [1]. In this case the point triangle relation allows us to design a linear Delaunay refinement algorithm. 3. Notice that the point triangle relation is not univocal throughout the whole process, since because of the swapping of the diagonals of pairs of triangles, it is possible to have more than one ....

.... bounds obtained for the pure longest side refinement algorithm are also valid in this context) It can also proved that, since we are working over a good quality triangulation (the smallest angle is bounded) the Delaunay insertion of each new point means a bounded number of diagonal swappings [1,8].2 5 NUMERICAL RESULTS AND CONCLUDING REMARKS The triangulations of Figures 4(a) and 4(b) illustrate the refined triangulations obtained, respectively, with the mixed Delaunay algorithm applied to solve the triangulation refinement problem over a square and a circular refinement region, starting ....

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

....are Delaunay triangulation and data dependent triangulation. Delaunay triangulation is a purely two dimensional 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 [13, 21]. 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 [8, 31] It can achieve lower error approximations than Delaunay triangulation, but it generates more slivers. 2. ....

....and perform incremental Delaunay triangulation. The routine Mesh Insert locates the triangle containing a given point, splits the triangle into three, and then recursively checks each of the outer edges of these triangles, flipping them if necessary to maintain a Delaunay triangulation (Figure 4) [13]. Mesh Insert(Point p) Insert p as a vertex in the Delaunay mesh Mesh Locate(Point p) Find the triangle in the mesh containing point p Locate and Interpolate(Point p) Locate the triangle containing point p and interpolate there Insert(Point p ) mark p as used Mesh Insert(p) Error(Point p ....

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

....a triangulation of the points that is constrained to include all the input edges. CDT preserves the properties of DT over all the constrained triangulations. We have implemented an incremental CDT algorithm that is a simple extension of the incremental DT algorithm described by Guibas and Stolfi [11]. An alternative easy to implement algorithm is described in the excellent survey by Bern and Eppstein [2] For each input polygonwe provide the CDT routine with all of its boundary edges and discontinuity segments. The corners of all the leaf nodes in the corresponding hierarchy are given as ....

....element methods [27] Six radiance values are computed for each element: three at the vertices, and three at the edge midpoints. Except for D 0 edges, these values are shared between adjacent faces (our CDT algorithm constructs a topological data structure suitable for such information sharing [11]. The six values are then interpolated by a quadratic bivariate polynomial. This scheme yields a C 0 piecewise quadratic interpolant to the radiance on each polygon. This interpolant was found to provide approximations that look smoother and are less prone to Mach bands than the traditional ....

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

....implementation, we extend such arcs only from points of tangency of original circles with great circles through the poles. 4 Fig. 1. Partial trapezoidal decomposition of an arrangement of small circles on an atom sphere. We represent the arrangements of the circles using a quad edge structure [13]. Once we obtain the arrangements for all atom spheres, we go on to construct the (van der Waals, or solvent accessible) molecular surface. This is achieved by adjusting the individual atom arrangements so as to retain only the faces in those arrangements that contribute to the outer surface, and ....

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.

....our system invokes a standard linesweep algorithm, as a preprocessing step, for computing the hierarchy and re orienting all the polygons in the correct directions. The internal representation of the contours that our system uses is the quad edge data structure described by Guibas and Stolfi [14]. This is done for maintaining efficiently the constructed polyhedral boundary of the interpolating solid object. In what follows, unless otherwise specified, we restrict our attention to a single pair of successive slices, and describe the manner in which the algorithm constructs an interpolating ....

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.

....Matching By using the unimodality property, we can find the maximum area intersection of a convex, n vertex polyhedron K with a plane perpendicular to the first coordinate axis. If the vertices, edges, and faces of K are stored in a standard data structure, such as the winged edge [2] quad edge [9], or doubly connected edge list [14] then our algorithm runs in O(n) time. Figure 2: A drum. We begin by defining a special class of polyhedra that have quadratic sectional area function A(x) A polyhedron is a drum if all of its vertices lie on two planes perpendicular to the x axis. Figure 2 ....

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

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

....are free along the line drawn through the pair of points. This precludes the case in which one direction is cannot be extended; although edge visibility actually changes for this case, it does not represent a critical change in information. Our implementation uses the quad edge structure from [5] to efficiently maintain the topological ordering of the conservative cells. Figure 7.a shows a computed example of the cell decomposition. The next issue is searching the information space for a solution, which corresponds to specifying a sequence of adjacent cells. The solution strategy must ....

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

....is simultaneously incident) Let S denote the set of external fragments for the segments in S. The method we use to implement the above strategy is to construct a representation of S 0 , the vertical decomposition of S[ ffi(H) using, say, the quad edge data structure of Guibas and Stolfi [14]) We call S 0 the pixel clipped arrangement of the segments in S. Note that none of segments in S [ ffi(H) cross (although there will be intersections defined by fragment endpoints and hot pixel boundaries) Moreover, the combinatorial complexity of S 0 is proportional to the snap rounded ....

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.

No context found.

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