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

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout