3
$\begingroup$

I want to implement a delaunay triangulator by using incremental building, which is purported to be $O(n \log(n))$ I am a little puzzled about 2 things.

Ever resource I read on the matter says:

  1. Make 3 points that are large enough to contain all other points.
  2. For each point, find the face that contains it, split that face to add the new point to the set, flip edges as needed to maintain the Delaunay condition.

But no resource I can find says how to actually generate those 3 points in a robust manner and no resource I can find says how to efficiently find the point face inclusion. A naive strategy to find the triangle that contains a point is linear in the number of triangles, that would not lead to $O(n\log n)$ so what am I missing?

$\endgroup$

2 Answers 2

3
$\begingroup$

These parts of the algorithm are discussed in the book Computational Geometry by de Berg et al. I will provide a summary here. Let $P$ be the set of input points.

  1. Make 3 points that are large enough to contain all other points.

This is not sufficient1. We need to find three points (some of them not in $P$) such that the triangle of them contains all points in $P$ and the Delaunay triangulation is still correct after removing any the points not in $P$. In particular, the second condition means any additional points should not lie inside a circle defined by three points in $P$.

The book chooses $p_{-2},p_{-1},p_0$ as the vertices of the triangle, where

  • the point $p_0$ is the leftmost highest point of $P$,
  • the point $p_{-1}$ lies far enough to the right on a horizontal line below all points of $P$ to lie outside every circle defined by three points of $P$ and such that the clockwise order of the points in $P$ around $p_{-1}$ is equal to their lexicographic order,
  • the point $p_{-2}$ lies far enough to the left on a horizontal line above all points of $P$ to lie outside every circle defined by three points of $P\cup \{p_{-1}\}$ and such that the counter-clockwise order of the points of $P\cup \{p_{-1}\}$ is equal to their lexicographic order.

While it is possible to compute coordinates satisfying these requirement for $p_{-1}, p_{-2}$, these coordinates can be quite large, as triples that are almost collinear define a large circle. So, it is better to only use the points symbolically, by adapting the operations that may involve these points. The property that the (counter-)clockwise order around these points is equal to the lexicographic order is useful here. The book provides the details on how to implement this.

  1. For each point, find the face that contains it

For this, we maintain a point location structure $\mathcal{D}$ that is a DAG where the leaves correspond to triangles in the current triangulation and internal nodes to previous triangles that are now destroyed. Initially, $\mathcal{D}$ contains the triangle $p_{-2}p_{-1}p_0$. When inserting a point from $P$ or flipping an edge, the new triangles become leaves in $\mathcal{D}$ and we draw an arc from the destroyed triangle(s) to the new ones that replace them in the triangulation.

We can find the triangle containing a point $p$ by starting at the root of $\mathcal{D}$, testing which of the child triangles contains $p$, until we reach a leaf node containing $p$, which corresponds to the triangle we need to find. Note that each internal node in $\mathcal{D}$ has at most three children, so the time required is linear in the depth of this DAG, or in other words, the number of triangles that contain the point $p$ and are placed before it.

Is the running time of this point-location method better than a linear search? If the DAG would be balanced, then its depth would be $O(\log n)$. This, however, is not necessarily the case, as there are insertion orders of $P$ that create an unbalanced DAG. Fortunately, there are "good" insertion orders and a random one is "good enough" in the sense that the total time required for point location with $\mathcal{D}$ is $O(n\log n)$ in expectation when given a random insertion order for $P$. See the book for a proof.


  1. Another option would be to try and "repair" the triangulation after removing a point. This seems more complicated than ensuring no errors are made in the first place.
$\endgroup$
0
$\begingroup$

Isn’t your problem simply: given a list of points $L$, create 3 new points such that all points in $L$ are enclosed by the triangle formed by the new 3 points?

If so, that can be done in linear time quite easily. For example if $b, t$ are the minimum and maximum $y$-coordinates in $L$ respectively, and $l, r$ are the minimum and maximum $x$-coordinates respectively, then $$ A = (l-1, b-1),\\ B = ((l+r)/2, t+1),\\C = (r+1, b-1) $$ should work as the new vertices.

$\endgroup$
2
  • $\begingroup$ this only answers half the question, the other part is how to find the trianglre containing a given point $\endgroup$
    – Makogan
    Aug 1, 2023 at 23:10
  • $\begingroup$ To obtain a triangulation for the original point-set, these three new points need to be removed eventually. If one of these points happens to lie inside the circle defined by 3 points in the input, then the graph obtained after removing these points and their incident edges may no longer be a triangulation. There may be ways to repair this, but I think it's better to choose the initial triangle such that this isn't a problem. $\endgroup$
    – Discrete lizard
    Aug 2, 2023 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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