In computational geometry, Delaunay triangulation is a widely used construct for creating a mesh of triangles from a set of points. One of the common tasks when dealing with Delaunay triangles is determining if a given triangle is internal or external. This determination is crucial for applications such as mesh generation, finite element analysis, and geographical information systems.

Understanding Delaunay Triangulation

Before determining whether a Delaunay triangle is internal or external, it's essential to grasp the fundamental properties of Delaunay triangulation:

1. Maximization of the Minimum Angle: Delaunay triangulations maximize the minimum angle of the triangles, avoiding sliver triangles.
2. Empty Circumcircle Property: For any triangle in a Delaunay triangulation, the circumcircle enclosing it contains no other points from the set.

Identifying Internal and External Triangles

Definitions

• Internal Triangle: A triangle is considered internal when all its edges are shared by adjacent triangles.
• External Triangle: A triangle is external if at least one of its edges is part of the convex hull of the point set, meaning it does not have three adjacent triangles.

Steps for Determination

1. Compute the Convex Hull: The first step is to determine the convex hull of the point set. Algorithms such as Graham's scan or Andrew's monotone chain algorithm can be used.
2. Check Triangle Edges: For each triangle, check if any of its edges are contained within the convex hull:
   • If an edge of a triangle matches an edge of the convex hull, the triangle is external.
   • If all edges are shared with neighboring triangles (none match the convex hull edge), the triangle is internal.

Example Walkthrough

Consider a set of points and a resulting Delaunay triangulation as follows:

• T1: Edges are (P1, P2), (P2, P3), (P1, P3). The edge (P1, P2) is part of the convex hull, thus `T1` is external.
• T2: Edges are (P2, P3), (P3, P4), (P2, P4). The edge (P2, P4) is part of the convex hull, indicating `T2` is external.
• T3: Edges are (P1, P3), (P3, P5), (P1, P5). The edge (P1, P5) is part of the convex hull, so `T3` is external.
• T4: Edges are (P3, P4), (P4, P5), (P3, P5), all edges are internal to the triangulation, categorizing `T4` as an internal triangle.
• Algorithm Complexity: Computing a convex hull has a computational complexity of $O(n \log n)$, where `n` is the number of points. Checking edge inclusion is a linear operation per triangle.
• Practical Usage: Understanding the nature of triangles helps in refining meshes for simulations and can identify boundary regions in graphical models.
• Degenerate Cases: Special attention is required when points are collinear or form degenerate triangles.