patternMinor
Efficiently finding point triangle inclusion when doing incremental delaunay triangulation?
Viewed 0 times
inclusionefficientlyincrementalpointdelaunaydoingtriangulationtrianglefindingwhen
Problem
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:
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?
Ever resource I read on the matter says:
- Make 3 points that are large enough to contain all other points.
- 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?
Solution
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.
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
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.
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.
- 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.
- 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.
- 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.
Context
StackExchange Computer Science Q#161388, answer score: 3
Revisions (0)
No revisions yet.