A Delaunay triangulation for a set $P$ of points in a plane is a triangulation $DT(P)$ such that no point in $P$ is inside the circumcircle of any triangle in $DT(P)$.

A Voronoi diagram is a partitioning of a plane into regions based on distance to points (called sites) in a specific subset of the plane.

We know that Delaunay triangulation is the dual of Voronoi diagram.

How can we prove that the boundary of Delaunay Triangulation is the convex hull of sites?

  • $\begingroup$ You need to clearly define the triangulation boundary - then you'll understand. Any triangulation, not only Delaunay one $\endgroup$ – HEKTO Dec 30 '16 at 18:40

We prove the following observation: The convex hull of P consists of those edges that are dual to the infinitely long Voronoi edges in the Voronoi diagram $VD(P)$, which again forms the outer face (boundary) of $DT(P)$.

To proof this take two point $p, q \in P$ with an infinite Voronoi edge $e$. Take the supporting line $\ell$ of $p, q$. Pick a center $o$ on $e$ and draw a circle $C$ centered at $o$ touching $p$ and $q$. By definition of $VD(P)$ there is no point of $P$ in $C$. We go with $o$ to infinity on $e$ to see that all points of $P$ are on the other side of $\ell$. So $\overline{pq}$ forms an edge of the convex hull and, as the dual of $e$, forms a boundary edge of $DT(P)$.

Empty half-space proofs convexity


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.