0
$\begingroup$

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)

  1. For i = h, h − 1, . . . , 0: Find a triangle ti from Ti that contains x.
  2. 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:

Voronoi Diagram

where green are our sites and red is our query point.

T0 is our delaunay triangulation 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: selected points U0

Remove these vertices and their edges:

T0 without U0

And now re-triangulate to obtain T1 ... how?

I'm assuming T1 should end up looking like this ...

maybe T1

But that got me thinking ...

Ultimately, the search algorithm given is

Search(x ∈ R2)

  1. For i = h, h − 1, . . . , 0: Find a triangle ti from Ti that contains x.
  2. return t0.

But if in the beginning, I would have set my red query point over here... moved query point

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.

T1? with moved query point

So that can't be T1.

I'd appreciate some help in understanding how Kirkpatrick's Hierarchy is constructed.

$\endgroup$
2
  • $\begingroup$ Hi. I want to know, how you created these figures? They look nice. $\endgroup$ Jun 22 at 15:23
  • $\begingroup$ @InuyashaYagami I'm afraid you're going to be disappointed ... they're google slides. I just googled a Voronoi Diagram and traced it so I could easily manipulate it to animate a step-by-step representation of the algorithm. $\endgroup$
    – User1291
    Jun 22 at 15:27
1
$\begingroup$

To make our life easier, we always assume that the convex hull of the triangulation consists of three points. If it is not, just add three points far away and triangulate. Then, the important thing is that those points that we remove are always internal points, never on this outerface that is a triangle. The reason why we want them to be independent, is because we want the following property: after removing the points, we obtain a triangulation with holes, and each hole is star shaped (there exists a point that sees all the edges of the hole). So no point can be on the boundary, and no two points removed are allowed to be adjacent. You still need to argue why you can have that many points.

This is why the convex hull of the triangulations is always the same, and we don't have the issue you mention

$\endgroup$

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.