Primitives for the manipulation of general subdivisions and the computation of Voronoi
From MaRDI portal
Publication:3711764
DOI10.1145/282918.282923zbMATH Open0586.68059OpenAlexW2052165970WikidataQ56047090 ScholiaQ56047090MaRDI QIDQ3711764FDOQ3711764
Authors: Jorge Stolfi, Leonidas Guibas 
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
Recommendations
computational geometrycomputational topologyconvex hullplanar graphspoint locationgeometric algorithmsEuler operatorsgeometric primitivesdata structure for generalized diagramsembeddings of graphs in two-dimensional manifoldsrepresentation of polyhedra
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cited In (only showing first 100 items - show all)
- Dynamic Trees and Dynamic Point Location
- Storing the subdivision of a polyhedral surface
- Axioms and hulls
- THE ANCHORED VORONOI DIAGRAM: STATIC, DYNAMIC VERSIONS AND APPLICATIONS
- Parallel computational geometry
- An algorithmic approach to some problems in terrain navigation
- USING LONGEST-SIDE BISECTION TECHNIQUES FOR THE AUTOMATIC REFINEMENT OF DELAUNAY TRIANGULATIONS
- COMPACT REPRESENTATIONS OF SIMPLICIAL MESHES IN TWO AND THREE DIMENSIONS
- HCPO: an efficient insertion order for incremental Delaunay triangulation
- Delaunay triangulation of arbitrarily shaped planar domains
- Fully dynamic Delaunay triangulation in logarithmic expected per operation
- Computing minimum length paths of a given homotopy class
- Fast point and element search method in adaptive remeshing procedure and its applications
- On Delaunay oriented matroids for convex distance functions
- Delaunay partitions in \(\mathbb R^n\) applied to non-convex programs and vertex/facet enumeration problems
- Order-k Voronoi diagrams of sites with additive weights in the plane
- Representing geometric structures in \(d\) dimensions: Topology and order
- Triangulating the surface of a molecule
- A linear-time algorithm for computing the Voronoi diagram of a convex polygon
- An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane
- Filling gaps in the boundary of a polyhedron
- A faster circle-sweep Delaunay triangulation algorithm
- An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations
- A nearly optimal deterministic parallel Voronoi diagram algorithm
- Combinatorial complexity bounds for arrangements of curves and spheres
- Randomized incremental construction of abstract Voronoi diagrams
- On the randomized construction of the Delaunay tree
- Planar minimally rigid graphs and pseudo-triangulations
- The power of geometric duality
- Local calculation of Voronoi diagrams
- Linear space data structures for two types of range search
- A new algorithm for shortest paths among obstacles in the plane
- On the stabbing number of a random Delaunay triangulation
- On maximum flows in polyhedral domains
- Triangulations in CGAL
- Voronoi Diagrams of Moving Points
- A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case
- Regular triangulations of dynamic sets of points
- OVERLAYING SURFACE MESHES, PART I: ALGORITHMS
- Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\)
- A faster divide-and-conquer algorithm for constructing Delaunay triangulations
- Applications of random sampling in computational geometry. II
- Triangulating a simple polygon in linear time
- Visibility-based pursuit-evasion in a polygonal environment
- Dynamic construction of abstract Voronoi diagrams
- EXACT ALGORITHMS FOR CIRCLES ON THE SPHERE
- Edge insertion for optimal triangulations
- The Safari interface for visualizing time-dependent volume data using iso-surfaces and contour spectra
- Pricing credit default swaps with bilateral value adjustments
- The complexity of cutting complexes
- An upper bound for conforming Delaunay triangulations
- Randomized incremental construction of Delaunay and Voronoi diagrams
- Topologically sweeping an arrangement
- Computing convolutions by reciprocal search
- Voronoi diagram with visual restriction
- A comparison of sequential Delaunay triangulation algorithms.
- Optimal and suboptimal robust algorithms for proximity graphs
- Expected time analysis for Delaunay point location
- Reverse search for enumeration
- On converting sets of tetrahedra to combinatorial and PL manifolds
- Construction of Voronoi diagrams in the plane by using maps
- Point placement algorithms for Delaunay triangulation of polygonal domains
- Arrangements on parametric surfaces. II: Concretizations and applications
- Topological mesh operators
- Delaunay refinement algorithms for triangular mesh generation
- Theorem on four support vertices of a polygonal line
- Primitives for the manipulation of three-dimensional subdivisions
- Triangulating a nonconvex polytope
- An optimal bound for high-quality conforming triangulations
- Tight bounds for connecting sites across barriers
- A Robust Implementation for Three-Dimensional Delaunay Triangulations
- The stochastic walk algorithms for point location in pseudo-triangulations
- A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works
- An optimal visibility graph algorithm for triangulated simple polygons
- AN IMPROVED ALGORITHM FOR SUBDIVISION TRAVERSAL WITHOUT EXTRA STORAGE
- Voronoi diagrams of moving points in higher dimensional spaces
- Verifiable implementations of geometric algorithms using finite precision arithmetic
- Using bigraphs to model topological graphs embedded in orientable surfaces
- TetGen, a Delaunay-based quality tetrahedral mesh generator
- Title not available (Why is that?)
- IMPROVEMENTS OF THE INCREMENTAL METHOD FOR THE VORONOI DIAGRAM WITH COMPUTATIONAL COMPARISON OF VARIOUS ALGORITHMS
- Decomposing the boundary of a nonconvex polyhedron
- A data modeling abstraction for describing triangular mesh algorithms
- Reprint of: Extreme point and halving edge search in abstract order types
- Algorithms and Computation
- Extreme point and halving edge search in abstract order types
- Title not available (Why is that?)
- Extending the doubly linked face list for the representation of 2-pseudomanifolds and 2-manifolds with boundaries
- A Methodology for Automated Cartographic Data Input, Drawing and Editing Using Kinetic Delaunay/Voronoi Diagrams
- CARTESIAN PRODUCT OF SIMPLICIAL AND CELLULAR STRUCTURES
- Voronoi diagrams with barriers and on polyhedra for minimal path planning
- Voronoi diagrams of rigidly moving sets of points
- Remarks on the computation of the horizon of a digital terrain
- Decomposing the boundary of a nonconvex polyhedron
- The embracing Voronoi diagram and closest embracing number
- A simple quality triangulation algorithm for complex geometries
- Subdivisions de surfaces et cartes généralisées de dimension 2
- Homology of cellular structures allowing multi-incidence
- Modeling and manipulating cell complexes in two, three and higher dimensions
- Reprint of: Delaunay refinement algorithms for triangular mesh generation
This page was built for publication: Primitives for the manipulation of general subdivisions and the computation of Voronoi
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3711764)
