Planar Straight Line Graphs:Glossary
Glossary
Arrangements. Given a collection of lines, we split each line into edges by inserting a vertex at every intersection on the line. The resulting PSLG is called the arrangement of lines. The arrangement of line segments is similarly defined.
Voronoi diagram. Let S be a set of points in the plane. For each point p ∈ S, the Voronoi region of p is defined to be {x ∈ R2 : p − x ≤ q − x , ∀q ∈ S}. The Voronoi diagram of S is the collection of all Voronoi regions (including their boundaries).
Triangulation. Let S be a set of points in the plane. Any maximal PSLG with the points in S as vertices is a triangulation of S.
Delaunay triangulation. Let S be a set of points in the plane. For any three points p, q, and r in S, if the circumcircle of the triangle pqr does not strictly enclose any point in S, we call pqr a Delaunay triangle. The Delaunay triangulation of S is the collection of all Delaunay triangles (including their boundaries). The Delaunay triangulation of S is the dual of the Voronoi diagram of S.
Comments
Post a Comment