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

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

....developed O(n log m n) algorithms for the three dimensional case which is particularly interesting because of the close relation to the two dimensional versions of the problems of computing the Voronoi diagram and the Delaunay triangulation of a set of N points. Using the reduction described in [55] the 3 d convex hull algorithm immediately gives algorithms for the two latter problems with the same I O performance. The O(n log m n) solution to the EPD problem discussed in the last section, which lead to the segment sorting and the red blue line segment intersection algorithms, has several ....

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.

....the mesh in a fully consistent state. It is worth noting that this method of managing subhulls may mean that the mesh as a whole would lose its Delaunay property, due to some of the boundary edges being nonoptimal as triangulation edges. This can be corrected by applying an edge flipping algorithm [GS85] to the boundary edges, although this was not implemented by the author. 6.2.2 Results for subhulls To test the effect that subhulls have on our algorithm, we perform a test similar to the one shown in Figure 6.2. Figure 6.12 shows a sample scene, where the shadow of a cheque lies on a book which ....

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.

....outside the boundaries of the image, and thus obtain data closer to the image edges. Alternatively, we could use smaller ellipses near the image edges. 4.2 Triangulation We then construct a constrained Delaunay triangulation, using the ellipse centers as vertices. We use an incremental algorithm [8, 9], 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 Transactions on Graphics Vol. 4, No. 2, April 1985. pp. 74--123.

....both parallel and sequential, are based on the divide and conquer paradigm. These algorithms can be characterized by the relative costs of the divide and merge phases. An early sequential approach developed by Shamos and Hoey [21] for Voronoi diagrams) and refined by Guibas and Stolfi [13] (for Delaunay triangulation) is to divide the point set into two subproblems using a median, then to find the Delaunay diagram of each half, and finally to merge the two diagrams. The merge phase does most of the work of the algorithm and runs in O(n) time, so the whole algorithm runs in O(n log ....

....that the number of internal points is reduced by a factor of at least two at each call. This simple separation is at the heart of our algorithm being efficient. Unlike early divide and conquer strategies for Delaunay triangulation which do most of the work when returning from recursive calls [21, 13, 8], this algorithm does all the work before making recursive calls. To find the separating path (which we call H) we project the points onto a paraboloid whose center is on the median line L, then project the points horizontally onto a vertical plane whose intersection with the x y plane is L (see ....

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.

....dynamically, subject to edge insertion and deletion, vertex insertion and deletion, as well as the insertion or deletion of a monotone chain of k edges. In addition, we are also interested in operations that are duals to edge insertion and deletion, as in the framework of Guibas and Stolfi [25], where we allow for vertex expansion and contraction: an expansion splits a vertex v into two new vertices connected by an edge, and a contraction merges two adjacent vertices into a new vertex. These operations are useful in applying a dynamic point location to spatial point location in ....

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

....triangulation . incremental triangulation . pliant mesh generation with post triangulation . pliant mesh generation with retriangulation Collective triangulation methods (Figure 1) choose the initial node positions, triangulate them as a whole, typically using Delaunay triangulation [11, 9], and then optionally adjust node positions using Laplacian smoothing. The principal difficulty with the collective approach is that poor choice of initial node positions can constrain the mesh to a poor topology. Incremental triangulation methods (Figure 2) insert nodes one at a time, updating ....

....computed. If the largest of these extents is greater than 1 then the corresponding edge is split at its midpoint and the mesh is retriangulated. Boundary nodes present in the input are never repositioned or deleted. Retriangulation after insertion is done using incremental Delaunay triangulation [11, 9]. In our context, point location is unnecessary because we know the edge being split. After deletion, we construct an initial triangulation of the resulting simple polygon and apply edge swapping to the edges internal to the polygon [3] 3.3 Node Tagging and Convergence This combination of ....

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

....two opposite halfedges, which makes this access again inefficient. The Minimal Rendering Tool MRT [3] 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 [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 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.

....experience, the object oriented solution applied in PlaNet is much more appropriate. 4 Algorithms So far, the algorithmic problems modeled with PlaNet mainly reflect our theoretical research interests. ffl Algorithms to compute a random triangulation and a Delaunay triangulation, respectively ([GS85], cf. Ede87, PS93] These algorithms are mainly intended to serve as a basis for random generation of instances. ffl Various smaller algorithms such as removing a random couple of edges, random paths, and the like. These procedures are mainly intended to support flexible random instance ....

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.

....of the map. Since the cases are abstractions of the map, we expect m to be much smaller than the size of the map, which contains 25,000 street segments. Conforming Delaunay Triangulation. Delaunay triangulations can be formed in O(n lg n) time, where n is the number of points in the triangulation [8]. Points occur at the endpoints of cases and at the initial and goal points. The number of additional points added to split segments is linear in practice 2 . Hence, n 2 O(m) and this step takes O(m lg m) time. Since the triangulation is planar, the number of edges E in the triangulation is ....

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.

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

....of line segments are output in order along the isoline component, which is necessary if smoothing is done. The map that is obtained is the structured isoline map. The method makes use of a network structure for the TIN, which can be a doubly connected edge list [20, 23] a quad edge structure [12], or a topological polygon network structure [3] We will describe an easier variant that makes use of the fact that a TIN is already quite structured, see also Peucker [21] for similar data structures. For our purposes, an extension is needed which will also be described. a b c d e Figure 3: ....

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

....amortized running time per update can be reduced to O(log n) by increasing the space to O(n 2 ) 6] 1. 1 New Results We further simplify the data structures used by Giammarresi and Italiano [6] that are straight forward implementations of the planar subdivision primitives of Giubas and Stolfi [7]. We introduce a new abstract data structure IncidenceDS to maintain the incidence relation between the vertices and faces of a plane graph during the edge deletions. Implementing this incidence data structure by different means, we get different total update time for all deletions. If we use ....

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

.... in the face [4] Yamaguchi and Tokieda, taking a different approach, allow multi connected faces by introducing of bridge edges [32] Many variations on these data structures have been used since, including as M antyl a s half edge data structure [15] Guibas and Stolfi s quad edge representation [7], and Hanrahan s face edge representation [8] Nonmanifold representations, such as Weiler s radial edge data structure, Karasick s star edge data structure, and Vanecek s fedge based data structure, have been introduced in [31, 12, 30] Any of these boundary data structures can be converted to a ....

L. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computations of voronoi diagrams. ACM Transactions on Graphics, pages 74--123, April 1985.

.... fi 1 1 Delta Delta Delta 1 p 1 p 2 Delta Delta Delta p d 2 p 1 2 p 2 2 Delta Delta Delta p d 2 2 fi fi fi fi fi fi where p k 2 : P d i=1 x k;i 2 for a point p k = x k;1 ; x k;d ) The determinant defining was called the InCircle predicate by Guibas and Stolfi [11] (see also [14, x17] and used as the basic primitive for computing Delaunay triangulations. Its value is zero if and only if the points lie in a hyperplane or hypersphere. If not, let p 1 ; p d 1 be in general position and let C be the unique hypersphere passing through them. Then, p 1 ....

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.

....embedding. Topology defines vertices, edges and faces of objects, as well as theirs incidence relationships. Embedding concerns the position and shape of these cells. Combinatorial embedded maps supply an easy, precise and concise description of subdivisions [13] Interest of topology was shown in [14] that presents a good alternative to describe subdivisions and topological operators. 3 Formal specification of subdivisions Let us recall that a combinatorial map is a triplet (B; ff 0 ; ff 1 ) where B is a finite set of darts, ff 0 is an involution on B without fixed points, i.e. a permutation ....

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

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.

Documents 201 to 219  Previous 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