Terminology
Here is a short table describing some terminology used throughout the package. Note that these definitions are only for two dimensions.
| Term | Definition |
|---|---|
| Triangulation | A subdivision of a point set $\mathcal P$ into a set of non-intersecting triangles. (To be more precise, it is the maximal planar subdivision of $\mathcal P$ whose vertex set is $\mathcal P$.) |
| Tessellation | A complete tiling of a plane by non-overlapping polygons. |
| Ghost | A geometric object is a ghost if it is referring to, or is related to, a point at infinity, such as a ghost vertex, ghost edge, or a ghost triangle. |
| Solid | A geometric object is solid if it is not a ghost. |
| Vertex | A vertex $v_k$ is the integer associated to some point $p_k$ in a given point set $\mathcal P$. |
| Point | A point $p$ is some coordinate $(x, y)$ in the plane $\mathbb R^2$. |
| Edge | An edge $e_{ij}$ is a tuple of vertices $e_{ij} = (i, j)$ referring to two connected points in the plane; whether the order of the edge matters depends on the context. |
| Triangle | A triangle $T_{ijk}$ is an ordered triplet of vertices $T_{ijk} = (i, j, k)$ defining edges $e_{ij}$, $e_{jk}$, and $e_{ki}$ in the plane representing a triangle. |
| Segment | A segment is an edge $e_{ij}$ that is constrained to the plane, i.e. it cannot be replaced (except by other collinear segments, provided $e_{ij}$ remains a union of its replacements). |
| Boundary | The set of lines covering a given domain. |
| Pole of Inaccessibility | The point that is furthest from a given boundary. |
| Graph | A graph is a pair $\mathcal G = (\mathcal V, \mathcal E)$, where $\mathcal V$ is the set of vertices and $\mathcal E$ is the set of edges; whether the orientation of the edges matters depends on the context. |
| Adjacent | An adjacent map is a map $\mathcal A \colon \mathcal E \to \mathcal V$ from edges $\mathcal E$ to vertices $\mathcal V$, such that an edge $e_{ij}$ is mapped to a vertex $v_k$ according to some geometrical relationship, e.g. for Delaunay triangulations the vertex $v_k$ is such that $T_{ijk}$ is a positively oriented triangle in the triangulation. |
| Adjacent2Vertex | An adjacent-to-vertex map is a map $\mathcal A^\dagger \colon \mathcal V \to \mathcal S \subseteq \mathcal E$ from vertices $\mathcal V$ to a set of edges $\mathcal S \subseteq \mathcal E$ that together define triangles in the plane, e.g. for Delaunay triangulations each edge $e_{jk} \in \mathcal S$ associated with a vertex $v_i$ define a positively oriented triangle $T_{ijk}$. |
| Bowyer Watson | The name given to the algorithm used for computing unconstrained Delaunay triangulations; see here. |
| Delaunay | The namesake of the Delaunay triangulation. |
| Voronoi | The namesake of the Voronoi tessellation. |
| Delaunay Property | The Delaunay property refers to both triangles and edges. Given a point set $\mathcal P$, a triangle $T_{ijk}$ is Delaunay if $p_i, p_j, p_k \in \mathcal P$ and its open circumcircle, $C_{ijk}$, contains no points in $\mathcal P$. An edge $e_{ij}$ is Delaunay if $p_i, p_j \in \mathcal P$ and its open circumcircle is empty. |
| Delaunay Triangulation | Given a point set $\mathcal P$ and a triangulation $\mathcal T(\mathcal P)$ of $\mathcal P$, if each triangle $T_{ijk} \in \mathcal P(\mathcal P)$ is Delaunay then the triangulation is said to be a Delaunay triangulation, denoted $\mathcal D\mathcal T(\mathcal P)$. |
| Voronoi Polygon | Given a point set $\mathcal P$ and a generator $v_i$, the Voronoi polygon (also called a cell) $\mathcal V_i$ of $v_i$ is defined by $\mathcal V_i = \{p \in \mathbb R^2: \forall q \in \mathcal P, |p - p_i| \leq |q - p|\}$, meaning each point in the polygon is as close to the generator $p_i$ as to any other generator in $\mathcal P$. |
| Voronoi Tessellation | The Voronoi tessellation (or diagram) of a point set $\mathcal P$, denoted $\mathcal V(\mathcal P)$, is the union of all the Voronoi polygons of each generator $p \in \mathcal P$ and their boundaries. |
| Circumcircle | Given a triangle $T_{ijk}$, its circumcircle $C_{ijk}$ is the unique circle going through $p_i$, $p_j$, and $p_k$. |
| Circumradius | Given a triangle $T_{ijk}$, its circumradius is the radius of its circumcircle $C_{ijk}$. |
| Circumcenter | Given a triangle $T_{ijk}$, its circumcenter $c$ is the center of its circumcircle $C_{ijk}$. |
| Diametral Circle | Given an edge $e_{ij}$, its diametral circle is the circle which has $e_{ij}$ as its diameter. |
| Diametral Lens | Given a lens angle $\theta$ and an edge $e_{ij}$, its diametral lens is defined as follows: Draw a line from $p_i$ towards some point $q$ which is left of $e_{ij}$ and on $e_{ij}$'s perpendicular bisector $\ell$, such that the line is at an angle of $\theta$ with $e_{ij}$. Now do the same for a point $r$ right of $e_{ij}$. The intersection of the circles through the points $p_i$, $p_j$, $q$ and $p_i$, $p_j$, $r$, respectively, defines the diametral lens with angle $\theta$. |
| Convex Hull | The convex hull of a point set $\mathcal P$, denoted $\mathcal C\mathcal H(\mathcal P)$, is the smallest convex set containing $\mathcal P$. |
| Curve | A curve can either refer to the a single connected part of a boundary, or to a parametric curve defining a section of a boundary. |
| Section | A portion of a boundary curve. |
| Refinement | The process of improving the quality of a triangulation by splitting segments and triangles. |
| Radius-edge Ratio | The radius-edge ratio of a triangle $T_{ijk}$ is $r/\ell_{\min}$, where $r$ is $T_{ijk}$'s circumradius and $\ell_{\min}$ is the length of its shortest edge. |
| Inradius | The inradius of a triangle $T_{ijk}$ is the radius of the largest circle that can be inscribed inside $T_{ijk}$. |
| Centroid | The centroid of a point set $\mathcal P$ is the mean of all the points, i.e. the centroid is $c = (1/|\mathcal P)\sum_{p\in \mathcal P} p$. For a polygon, the centroid is a bit more complicated. |
| Sink | The sink $S_{ijk}$ of a triangle $T_{ijk}$ in some triangulation $\mathcal T(\mathcal P)$ is defined as follows: If its circumcenter $c$ is inside $T_{ijk}$, then its sink is $S_{ijk} = T_{ijk}$; if $T_{ijk}$ is on the boundary of $\mathcal T(\mathcal P)$, then $S_{ijk} = T_{ijk}$; if neither of the first two conditions are true, then $S_{ijk}$ is the sink of $V$, where $V$ is the triangle adjoining the edge of $T_{ijk}$ which intersects the line from $T_{ijk}$'s circumcenter to its centroid. |
| Generator | Given a Voronoi polygon $\mathcal V_i$, its generator is the associated vertex $v_i$. The point $p_i$ could also be called the generator. |
| Predicate | A predicate is some test of a geometrical property. |
| Certificate | A certificate is the result returned from a predicate. |
| Orientation | Orientation refers to the arrangement of a given set of points in the plane defining a boundary. The boundary is said to be positively oriented if you could walk along the points and also have the interior on the left, negatively oriented if the interior would be on the right. If the boundary is a straight line, the orientation is said to be degenerate. |