Ok, so I'm having bit of an issue understanding nearest neighbour search with delaunay triangulation.
In particular, how do I re-triangulate my delaunay triangulations once I introduced holes?
But I should probabl provide a bit of context:
(source: university script, not sure I should/am allowed to link to it, so please just take my word for it that this is how it's explained therein. [I'm skipping most of the proofs here because they aren't relevant to the question I'm having.])
Theorem 10.17 Given a triangulation T for a set P ⊂ R2 of n points, one can build in O(n) time an O(n) size data structure that allows for any query point q ∈ conv(P) to find in O(log n) time a triangle from T containing q. The data structure we will employ is known as Kirkpatrick’s hierarchy.
We will now the develop the data structure for point location in a triangulation, as described in Theorem 10.17.
The main idea is to construct a hierarchy T0,. . . ,Th of triangulations, such that
- T0 = T [= Delaunay Triangulation],
- the vertices of Ti are a subset of the vertices of Ti−1, for i = 1, . . . , h, and
- Th comprises a single triangle only.
Search(x ∈ R2)
- For i = h, h − 1, . . . , 0: Find a triangle ti from Ti that contains x.
- return t0.
This search is efficient under the following conditions.
(C1) Every triangle from Ti intersects only few (>= c) triangles from Ti−1. (These will then be connected via the data structure.)
(C2) h is small (>= d log n).
Ok, I get the idea behind it, I'm not certain about the actual implementation. Let's read on:
Our working plan is to obtain Ti from Ti−1 by removing several independent (pairwise non-adjacent) vertices and re-triangulating. These vertices should
a) have small degree (otherwise the degree within the hierarchy gets too large, that is, we need to test too many triangles on the next level) and
b) be many (otherwise the height h of the hierarchy gets too large).
Lemma 10.22 In every triangulation of n points in R2 there exists an independent set of at least ⌈n/18⌉ vertices of maximum degree 8. Moreover, such a set can be found in O(n) time
Let W ⊆ V denote the set of vertices of degree at most 8. Claim: |W| > n/2
Construct an independent set U in T as follows (greedily): As long as W != ∅, add an arbitrary vertex v ∈ W to U and remove v and all its neighbors from W.
Obviously U is independent and all vertices in U have degree at most 8.
Construct the hierarchy T0, . . . Th with T0 = T as follows.
Obtain Ti from Ti−1 by removing an independent set U as in Lemma 10.22 and re-triangulating the resulting holes.
Alright, let's try this out. Let's say we have a voronoi diagram like so:
where green are our sites and red is our query point.
T0 is our delaunay triangulation
Let's construct our first set of independent vertices U0. As all vertices have degree < 8, we can pick any we want, but we know from above that
These vertices should
a) have small degree (otherwise the degree within the hierarchy gets too large, that is, we need to test too many triangles on the next level) and
b) be many (otherwise the height h of the hierarchy gets too large).
So let's start with the leftmost vertex, which has degree 3, and take it from there:
Remove these vertices and their edges:
And now re-triangulate to obtain T1 ... how?
I'm assuming T1 should end up looking like this ...
But that got me thinking ...
Ultimately, the search algorithm given is
Search(x ∈ R2)
- For i = h, h − 1, . . . , 0: Find a triangle ti from Ti that contains x.
- return t0.
But if in the beginning, I would have set my red query point over here...
That would still be within the convex hull of T0 (our delaunay triangulation), BUT we'd have no way to find a triangle in T1 that contains it.
So that can't be T1.
I'd appreciate some help in understanding how Kirkpatrick's Hierarchy is constructed.
