Generalized Delaunay triangulation for planar graphs
From MaRDI portal
The Delaunay triangulation of a planar straight line graph has the property that the circumcircle of any triangle does not contain any other vertex in its interior. The authors introduce a generalized Delaunay triangulation such that this circumcircle contains no vertices which are visible from the three vertices of the triangle. It is shown that there exists a unique generalized Delaunay triangulation, and that the minimum angle of the triangles in the triangulation is maximum among all possible triangulations of the graph. Finally, an \(0(n^ 2)\) algorithm for the construction is presented where n is the number of vertices.
Recommendations
- scientific article; zbMATH DE number 6379407
- Outerplanar graphs and Delaunay triangulations
- Generalized Delaunay triangulations of non-convex domains
- Delaunay triangulation of arbitrarily shaped planar domains
- Constrained generalized Delaunay graphs are plane spanners
- Geodesic Delaunay triangulations in bounded planar domains
- Generalizing CGAL Periodic Delaunay Triangulations
- scientific article; zbMATH DE number 4174387
- scientific article; zbMATH DE number 4098181
- Generalized triangulations
Cites work
- A linear algorithm for computing the visibility polygon from a point
- A linear algorithm for finding the convex hull of a simple polygon
- An efficient algorithm for determining the convex hull of a finite planar set
- Automatic triangulation of arbitrary planar domains for the finite element method
- Finding the convex hull of a simple polygon
- Generalization of Voronoi Diagrams in the Plane
- scientific article; zbMATH DE number 4037201 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- Location of a Point in a Planar Subdivision and Its Applications
- On finding the convex hull of a simple polygon
- On the Angle Condition in the Finite Element Method
- Optimal Point Location in a Monotone Subdivision
- Optimal Search in Planar Subdivisions
- Piecewise Quadratic Approximations on Triangles
- Triangular Elements in the Finite Element Method
- Triangulating a simple polygon
- Two algorithms for constructing a Delaunay triangulation
- Two Dimensional Interpolation from Random Data
- Visibility of a simple polygon
- Visibility of disjoint polygons
Cited in
(88)- Constrained Delaunay triangulations
- On the geodesic Voronoi diagram of point sites in a simple polygon
- A space efficient greedy triangulation algorithm
- Voronoi diagrams with barriers and the shortest diagonal problem
- Fast algorithms for greedy triangulation
- Optimal time bounds for some proximity problems in the plane
- Detecting and decomposing self-overlapping curves
- Duality of constrained Voronoi diagrams and Delaunay triangulations
- Provably good mesh generation
- Point placement algorithms for Delaunay triangulation of polygonal domains
- Delaunay refinement algorithms for triangular mesh generation
- Structural tolerance and Delaunay triangulation
- Delaunay and Voronoi tessellations and minimal simple cycles in triangular region and regular-3 undirected planar graphs
- Approximating uniform triangular meshes in polygons.
- A framework for advancing front techniques of finite element mesh generation
- Generating free-form grid truss structures from 3D scanned point clouds
- On shape Delaunay tessellations
- Reprint of: Delaunay refinement algorithms for triangular mesh generation
- Geometric biplane graphs. I: Maximal graphs
- Fast segment insertion and incremental construction of constrained Delaunay triangulations
- Local properties of geometric graphs
- Pre-triangulations and liftable complexes
- General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties
- Fast greedy triangulation algorithms.
- Node-based parallel computing of three-dimensional incompressible flows using the free mesh method
- Preferred directions for resolving the non-uniqueness of Delaunay triangulations
- Representing stereo data with the Delaunay triangulation
- An optimal algorithm for realizing a Delaunay triangulation
- Outerplanar graphs and Delaunay triangulations
- scientific article; zbMATH DE number 6379407 (Why is no real title available?)
- Counting plane graphs with exponential speed-up
- 3D boundary recovery by constrained Delaunay tetrahedralization
- Diagonal swap procedures and characterizations of 2D-Delaunay triangulations
- scientific article; zbMATH DE number 5764872 (Why is no real title available?)
- A uniqueness theorem for Delaunay graphs
- A note on visibility-constrained Voronoi diagrams
- An $O(n^2 \log n)$ Time Algorithm for the Minmax Angle Triangulation
- Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time
- scientific article; zbMATH DE number 1240687 (Why is no real title available?)
- scientific article; zbMATH DE number 563688 (Why is no real title available?)
- Reliable Delaunay‐based mesh generation and mesh improvement
- A generalized Delaunay triangulation algorithm with adaptive grid size control
- scientific article; zbMATH DE number 1139074 (Why is no real title available?)
- Brittle fracture in polycrystalline microstructures with the extended finite element method
- On triangulation axes of polygons
- Characterizing Delaunay graphs via fixed point theorem: a simple proof
- MINIMAL SET OF CONSTRAINTS FOR 2D CONSTRAINED DELAUNAY RECONSTRUCTION
- On decomposition of embedded prismatoids in \(\mathbb{R}^3\) without additional points
- Fast algorithms for greedy triangulation
- A linear-time construction of the relative neighborhood graph within a histogram
- A Simple Algorithm to Triangulate a Special Class of 3d Non-convex Polyhedra Without Steiner Points
- Aligned plane drawings of the generalized Delaunay-graphs for pseudo-disks
- TetGen, a Delaunay-based quality tetrahedral mesh generator
- OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS
- Computational Science and Its Applications – ICCSA 2004
- Optimal Triangulation with Steiner Points
- Triangulations of Line Segment Sets in the Plane
- A FEM-BASED MESHFREE METHOD WITH A PROBABILISTIC NODE GENERATION TECHNIQUE
- Formal study of plane Delaunay triangulation
- Generalizing CGAL Periodic Delaunay Triangulations
- Essential constraints of edge-constrained proximity graphs
- On exclusion regions for optimal triangulations
- Sequences of spanning trees and a fixed tree theorem
- On one approach to the estimation of a triangular element degeneration in a triangulation
- Efficient computation of the geodesic Voronoi diagram of points in a simple polygon
- Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time
- Fast skeleton construction
- Shortcut hulls: vertex-restricted outer simplifications of polygons
- Optimal Area Polygonization by Triangulation and Visibility Search
- A spectral characterization of the Delaunay triangulation
- Conservative interpolation between unstructured meshes via supermesh construction
- An upper bound for conforming Delaunay triangulations
- A convex polygon among polygonal obstacle: Placement and high-clearance motion
- Efficiently updating constrained Delaunay triangulations
- The tight spanning ratio of the rectangle Delaunay triangulation
- Restricted constrained Delaunay triangulations
- From point patterns to networks: to what extent does the Delaunay triangulation reproduce key spatial and density information?
- Pointed binary encompassing trees: simple and optimal
- Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations
- A study on Delaunay terminal edge method
- Incrementally constructing and updating constrained Delaunay tetrahedralizations with finite precision coordinates
- Optimal triangulation of polygons
- Vertex-colored encompassing graphs
- Angle-monotonicity of Delaunay triangulation
- A linear-time algorithm for computing the Voronoi diagram of a convex polygon
- Realizability of Delaunay triangulations
- Generalized Delaunay triangulations of non-convex domains
- Flips in planar graphs
This page was built for publication: Generalized Delaunay triangulation for planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1078807)
