Primitives for the manipulation of general subdivisions and the computation of Voronoi

DOI10.1145/282918.282923zbMath0586.68059OpenAlexW2052165970WikidataQ56047090 ScholiaQ56047090MaRDI QIDQ3711764

Publication date: 1985

Published in: ACM Transactions on Graphics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/282918.282923

zbMATH Keywords

planar graphs geometric algorithms convex hull computational geometry geometric primitives computational topology point location Euler operators data structure for generalized diagrams embeddings of graphs in two-dimensional manifolds representation of polyhedra

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Optimal and suboptimal robust algorithms for proximity graphs, The Safari interface for visualizing time-dependent volume data using iso-surfaces and contour spectra, Computing minimum length paths of a given homotopy class, Point placement algorithms for Delaunay triangulation of polygonal domains, The power of geometric duality, Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\), Expected time analysis for Delaunay point location, HCPO: an efficient insertion order for incremental Delaunay triangulation, Computing convolutions by reciprocal search, Polygonizations of point sets in the plane, A faster divide-and-conquer algorithm for constructing Delaunay triangulations, A new algorithm for shortest paths among obstacles in the plane, Theorem on four support vertices of a polygonal line, On the stabbing number of a random Delaunay triangulation, A new representation of orientable 2-manifold polygonal surfaces for geometric modelling, An optimal bound for high-quality conforming triangulations, An optimal visibility graph algorithm for triangulated simple polygons, The complexity of cutting complexes, Primitives for the manipulation of three-dimensional subdivisions, Parallel computational geometry, Verifiable implementations of geometric algorithms using finite precision arithmetic, An algorithmic approach to some problems in terrain navigation, Computing half-plane and strip discrepancy of planar point sets, Reverse search for enumeration, Boundary layer mesh generation with fast collision detection, Topologically sweeping an arrangement, On Delaunay oriented matroids for convex distance functions, Decremental 2- and 3-connectivity on planar graphs, Erased arrangements of linear and convex decompositions of polyhedra, Optimal tetrahedralization of the 3D-region ``between a convex polyhedron and a convex polygon, Using bigraphs to model topological graphs embedded in orientable surfaces, Reprint of: Extreme point and halving edge search in abstract order types, Untangling planar curves, On converting sets of tetrahedra to combinatorial and PL manifolds, Arrangements on parametric surfaces. II: Concretizations and applications, A hierarchical representation and computation scheme of arbitrary-dimensional geometrical primitives based on CGA, Fast point and element search method in adaptive remeshing procedure and its applications, Efficient representation of Laguerre mosaics with an application to microstructure simulation of complex ore, Topological mesh operators, A fast algorithm for computing irreducible triangulations of closed surfaces in \(\mathbb{E}^d\), A faster circle-sweep Delaunay triangulation algorithm, Reachable region query and its applications, The stochastic walk algorithms for point location in pseudo-triangulations, Remarks on the computation of the horizon of a digital terrain, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, A divide-and-conquer algorithm for constructing relative neighborhood graph, Triangulating a nonconvex polytope, Interior boundary-aligned unstructured grid generation and cell-centered versus vertex-centered CVD-MPFA performance, Combinatorial complexity bounds for arrangements of curves and spheres, On maximum flows in polyhedral domains, Triangulating a simple polygon in linear time, Minimal length tree networks on the unit sphere, Delaunay triangulation of arbitrarily shaped planar domains, Randomized incremental construction of Delaunay and Voronoi diagrams, Filling gaps in the boundary of a polyhedron, Polynomial-reproducing spline spaces from fine zonotopal tilings, Decomposing the boundary of a nonconvex polyhedron, Computing bushy and thin triangulations, A data modeling abstraction for describing triangular mesh algorithms, Delaunay triangulations in three dimensions with finite precision arithmetic, An upper bound for conforming Delaunay triangulations, Randomized incremental construction of abstract Voronoi diagrams, Reprint of: Delaunay refinement algorithms for triangular mesh generation, Fully dynamic Delaunay triangulation in logarithmic expected per operation, Voronoi diagrams of rigidly moving sets of points, Tight bounds for connecting sites across barriers, Two simple algorithms for constructing a two-dimensional constrained Delaunay triangulation, On the randomized construction of the Delaunay tree, Delaunay partitions in \(\mathbb R^n\) applied to non-convex programs and vertex/facet enumeration problems, On shape Delaunay tessellations, Planar minimally rigid graphs and pseudo-triangulations, Tubular parametric volume objects: thickening a piecewise smooth 3D stick figure, Three-dimensional unstructured gridding for complex wells and geological features in subsurface reservoirs, with CVD-MPFA discretization performance, Linear space data structures for two types of range search, A distributed algorithm to maintain a proximity communication network among mobile agents using the Delaunay triangulation, Distributed combinatorial maps for parallel mesh processing, Representing geometric structures in \(d\) dimensions: Topology and order, An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations, Construction of Voronoi diagrams in the plane by using maps, Bisectors of linearly separable sets, A nearly parallel algorithm for the Voronoi diagram of a convex polygon, A nearly optimal deterministic parallel Voronoi diagram algorithm, Spheres, molecules, and hidden surface removal, An \(O(n^{5/2}\log n)\) algorithm for the rectilinear minimum link-distance problem in three dimensions, Storing the subdivision of a polyhedral surface, Coupled fluid-structure solver: the case of shock wave impact on monolithic and composite material plates, Voronoi diagrams with barriers and on polyhedra for minimal path planning, Applications of random sampling in computational geometry. II, Transforming curves on surfaces, Efficiently solving the traveling thief problem using hill climbing and simulated annealing, A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case, Practical unstructured splines: algorithms, multi-patch spline spaces, and some applications to numerical analysis, A new bound for map labeling with uniform circle pairs, A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works, Order-k Voronoi diagrams of sites with additive weights in the plane, Triangulations in CGAL, Delaunay refinement algorithms for triangular mesh generation, Merging in maps and in pavings, Liftings and stresses for planar periodic frameworks, Regular triangulations of dynamic sets of points, DIMENSION-INDEPENDENT BSP (2): BOUNDARY-TO-INTERIOR MAPPING, Covering grids and orthogonal polygons with periscope guards, Voronoi diagrams over dynamic scenes, Edge insertion for optimal triangulations, EXTENDING THE DOUBLY LINKED FACE LIST FOR THE REPRESENTATION OF 2-PSEUDOMANIFOLDS AND 2-MANIFOLDS WITH BOUNDARIES, Solides non organisés : définition, implantation et plongement, USING LONGEST-SIDE BISECTION TECHNIQUES FOR THE AUTOMATIC REFINEMENT OF DELAUNAY TRIANGULATIONS, Dynamic 2- and 3-connectivity on planar graphs, Voronoi diagrams of moving points in higher dimensional spaces, A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon, AN IMPROVED ALGORITHM FOR SUBDIVISION TRAVERSAL WITHOUT EXTRA STORAGE, Extreme point and halving edge search in abstract order types, Maintaining proximity in higher dimensional spaces, Visibility-based pursuit-evasion in a polygonal environment, The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs, Unnamed Item, Voronoi diagram with visual restriction, Unnamed Item, An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane, Polygon placement under translation and rotation, OVERLAYING SURFACE MESHES, PART I: ALGORITHMS, Modeling and Manipulating Cell Complexes in Two, Three and Higher Dimensions, CARTESIAN PRODUCT OF SIMPLICIAL AND CELLULAR STRUCTURES, A comparison of sequential Delaunay triangulation algorithms., Decomposing the boundary of a nonconvex polyhedron, COMPACT REPRESENTATIONS OF SIMPLICIAL MESHES IN TWO AND THREE DIMENSIONS, EXACT ALGORITHMS FOR CIRCLES ON THE SPHERE, A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING, Subdivisions de surfaces et cartes généralisées de dimension 2, Efficient Node Overlap Removal Using a Proximity Stress Model, Triangulating the surface of a molecule, Dynamic construction of abstract Voronoi diagrams, A Methodology for Automated Cartographic Data Input, Drawing and Editing Using Kinetic Delaunay/Voronoi Diagrams, A simple quality triangulation algorithm for complex geometries, HANDLEBODY REPRESENTATION FOR SURFACES AND ITS APPLICATIONS TO TERRAIN MODELING, Graph exploration with robot swarms, Dynamic Trees and Dynamic Point Location, Gathering by Repulsion., A Robust Implementation for Three-Dimensional Delaunay Triangulations, Voronoi Diagrams of Moving Points, TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator, Homology of cellular structures allowing multi-incidence, Fast segment insertion and incremental construction of constrained Delaunay triangulations, Extended graph rotation systems as a model for cyclic weaving on orientable surfaces, Pricing credit default swaps with bilateral value adjustments