Divide-and-Conquer Algorithm for Delaunay Triangulation
Delaunay triangulation using a divide-and-conquer approach involves sorting input sites, dividing them into halves, recursively building Delaunay for each half, adding cross edges between the halves, and recombining by removing certain edges. Key steps include building cross edges in linear time and adding Delaunay edges bottom-up. Visualization using circular bubbles aids in understanding the process.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
A Divide-and-Conquer Algorithm for Delaunay Triangulation CS 268 @ Gates 219 October 17, 3:00 4:20 Disclaimer: All figures in the slides are for illustration only. Best approximations were attempted, but preciseness or correctness of the geometric constructions should not be assumed. Richard Zhang (for Leo G.) 1
Algorithm pipeline 1. Sort n input sites by their x-coordinates x 2
Algorithm pipeline 2. Divide the n sites into two equal halves x 3
Algorithm pipeline 3. Recursively build Delaunay, L & R, for each half R L x 4
Algorithm pipeline 3. Recombine by adding cross edges between L & R R L x 5
Algorithm pipeline 3. Recombine by adding cross edges between L & R Some LL or RR edges may be deleted R L x 6
Key step: build cross edges (linear time) Start with the lower common tangent of L s and R s convex hulls This edge is on the convex hull, hence a Delaunay edge R L x 7
Key step: build cross edges Add Delaunay edges bottom-up (ascending y-order) Given a current Delaunay edge (called a basel edge), the next Delaunay edge must share a vertex with the basel Lemma 28 R L x 8
Key step: build cross edges Lemma 28 proof sketch: We have a triangulation, the split line (dash) cuts through a series of triangles. Hence, two consecutive cross edges must belong to one triangle. R L x 9
Useful visualization: circular bubbles Think of all circles that pass through two end points of a basel To go from one such circle to another is like stretching a circular bubble by rising it through a chord (the basel) Fixed Basel = chord Fixed 10
Useful visualization: circular bubbles Think of all circles that pass through two end points of a basel To go from one such circle to another is like stretching a circular bubble by rising it through a chord (the basel) Fixed Basel = chord Fixed 11
Useful visualization: circular bubbles Think of all circles that pass through two end points of a basel Stretching on one side = shrinking on the other side stretch Fixed Basel = chord shrink Fixed 12
Some notations Us(AB): upper half plane Hs(AB): either Us(AB) or Ls(AB) Cir(XYZ): circle through X, Y, Z A basel B Ls(AB): lower half plane 13
Lemma 29 Consider truncated circles, Hs(AB) Cir(ABM) and Hs(AB) Cir(ABN) for any points M and N. One of them must entirely contain the other. either A N M B 14
Lemma 29 Consider truncated circles, Hs(AB) Cir(ABM) and Hs(AB) Cir(ABN) for any points M and N. One of them must entirely contain the other. N A M B or 15
Lemma 29 If Yellow contains Green on one side (Green to Yellow is a stretch), then Yellow is contained by Green on the other side (G to Y is a shrink). stretch N A shrink B M 16
N5 N4 N2 N3 N1 B A Lemma 30: characterize the candidate for next basel Consider a basel AB and let N1, , Nkbe A s L-neighbors in the upper half plane Us(AB), sorted in counterclockwise order. Note: some edges ANi may be interior edges in the Delaunay triangulation L. 17
N5 N4 N2 N3 N1 B A Lemma 30: characterize the candidate for next basel Consider all the i = Us(AB) Cir(ABNi) s, the truncated circles The containment of i+1 by i is unimodal in that there is a switching point j so that before j, i.e., i < j, we have: i i+1 And after j, i.e., i j, we have i i+1 18
Lemma 30 Specifically, in the example here, we have N5 N4 1 2 N2 N3 N1 B A 19
Lemma 30 Specifically, in the example here, we have N5 N4 2 3 N2 N3 N1 B A 20
Lemma 30 Specifically, in the example here, but then a switch at N3: N5 N4 3 4 N2 N3 N1 B A 21
Lemma 30 Then the containment does not switch back any more, we have N5 N4 4 5 N2 N3 N1 B A 22
N5 N4 L R N2 N3 N1 B A Lemma 30 The switching point N3is special. It is the candidate (on the L side) for B as the next basel. There is also a similar candidate on the R side for A, as the next basel. 23
N5 N4 L R N2 N3 N1 B A Lemma 30 If N3were chosen, then edges AN1and AN2would be deleted, since they cannot be Delaunary. N3becomes the next A to form the next basel edge. We will start at the new AB and repeat 24
N5 N4 L R N2 A N1 B Lemma 30 If N3were chosen, then edges AN1and AN2would be deleted, since they cannot be Delaunary. N3becomes the next A to form the next basel edge. We will start at the new AB and repeat 25
N5 N4 L R N2 N3 N1 B A A key observation about the switching point (used later) Since 3, the truncated circle Cir(ABN3) Us(AB) for the switching point,is contained by all the other s, ALL other N s, N1, N2, N4, , must lie outside of 3. 26
Proof of Lemma 30 The key is to look at intersection Xi between Cir(ANiNi+1) and line AB and noticing that they monotonically move toward A. N5 N4 N3 N2 N1 X1 A B 27
Proof of Lemma 30 The key is to look at intersection Xi between Cir(ANiNi+1) and line AB and noticing that they monotonically move toward A. N5 N4 N3 N2 N1 X1 X2 A B 28
Proof of Lemma 30 The switch (at N3) occurs when Xi crosses B N5 N4 N3 N2 N1 X1 X2 A B X3 29
Proof of Lemma 30 The switch (at N3) occurs when Xi crosses B Before crossing, Cir(ANiNi+1) contains B. Afterwards, B is outside. N5 N4 N3 N2 N1 X1 X2 A B X3 30
To prove monotonicity of the Xis: Look at ANY three consecutive points Ni-1, Ni, and Ni+1. Since ANi-1Ni is Delaunay, Ni+1 must lie outside Cir(ANi-1Ni). Consider ANi as the chord, to get from Cir(ANi-1Ni) to Cir(ANiNi+1), Cir(ANi- 1Ni) must be stretched through the chord. Ni+1 Ni Ni-1 Stretch B A Xi-1 Xi 31
To prove monotonicity of the Xis: Look at ANY three consecutive points Ni-1, Ni, and Ni+1. Recall Lemma 29, on the other side of ANi, Cir(ANi-1Ni) must be shrunk through the chord. Hence, the intersection Xi must move from Xi-1 toward A. Ni+1 Ni Ni-1 Stretch B A Xi-1 Xi Shrink 32
Lemma 31: how to choose the next Delaunay cross edge Let N be the L candidate and M be the R candidate for besal edge AB, which is the current Delaunay cross edge found. Let ABC be the current Delaunay triangle. Recall: N is the switching point in A s L-neighbors. M is the switching point in B s B-neighbors. L R N M A B C 33
Lemma 31: how to choose the next Delaunay cross edge Let N be the L candidate and M be the R candidate for besal edge AB, which is the current Delaunay cross edge found. Let ABC be the current Delaunay triangle. How to choose: If M is outside Cir(ABN), then BN is chosen instead of AM. Need to show that BN must be a Delaunay edge. L R N M A B C 34
Lemma 31 To show that BN is a Delaunay edge, we show Cir(ABN) is empty of ALL sites. First, look at the Ls(AB), the lower side of AB. Since ABC is Delaunay, ALL sites, including N, must lie outside Cir(ABC). Since N lies outside, in Ls(AB), Cir(ABN) is contained in Cir(ABC). So in the lower side, Cir(ABN) cannot contain any site. L R N M A B C 35
Lemma 31 To show that BN is a Delaunay edge, we show Cir(ABN) is empty of ALL sites. Now let us look at the Us(AB), the upper side of AB. Recall a previous key observation about the choice of switching point N. L R N M B A 36
Reminder slide N5 N4 L R N2 N3 N1 B A A key observation about the switching point (used now) Since 3, the truncated circle Cir(ABN3) Us(AB) for the switching point,is contained by all the other s, ALL other N s, N1, N2, N4, , must lie outside of 3. 37
L R N B A With N as the switching point, it is not hard to see: not any sites in the L side can lie inside Cir(ABN) in the upper side of AB. 38
L R N M B A Similarly, since M is the switching point on the R side for B, no R sites can lie inside Cir(ABM) in the upper side of AB. 39
L R N M B A Since M lies outside Cir(ABN) --- which was why BN was chosen over AM, Cir(ABN) lies inside of Cir(AMB) in Us(AB). Hence, no R sides can lie inside of Cir(ABN) in the upper side of AB. 40
Hence, in the upper side (of AB), Cir(ABN) cannot contain any site. Cir(ABN) cannot contain any site in either side of AB. BN is Delaunay. L Lemma 31 is proved. R N M B A 41
Now recall how we build cross edges Get lower common tangent of L s and R s convex hulls at first basel 1. For each basel edge AB, 2. Search for switching points on L and R sides. Let them be N for A and M for B. 1. Choose between N and M to determine the next basel edge, then repeat. 2. Stop when reaching the upper common tangent. 3. 42
Linear time. Straightforward scheme (see notes) visits only L and R hull vertices. Complexity analysis Get lower common tangent of L s and R s convex hulls at first basel 1. For each basel edge AB, 2. Search for switching points on L and R sides. Let them be N for A and M for B. 1. Choose between N and M to determine the next basel edge, then repeat. 2. Stop when reaching the upper common tangent. 3. 43
Complexity analysis Get lower common tangent of L s and R s convex hulls at first basel 1. For each basel edge AB, 2. Search for switching points on L and R sides. Let them be N for A and M for B. 1. Choose between N and M to determine the next basel edge, then repeat. 2. Stop when reaching the upper common tangent. 3. Do inCircle test. Constant time. 44
Complexity analysis Get lower common tangent of L s and R s convex hulls at first basel 1. For each basel edge AB, 2. Search for switching points on L and R sides. Let them be N for A and M for B. 1. Choose between N and M to determine the next basel edge, then repeat. 2. Stop when reaching the upper common tangent. 3. Only tricky analysis is this step. Need an amortized analysis. Recall that to search for the switching point N for the L (or A s) side, we simply need to perform a series of inCircle tests. 45
Reminder slide N5 N4 L R N2 New A = N3 N1 B A Lemma 30 If N3were chosen, then edges AN1and AN2would be deleted. N3becomes the next A, we will start at the basel AB and repeat To test for switching points, can do tests inCircle(A, B, Ni, Ni+1), etc. 46
Complexity analysis Get lower common tangent of L s and R s convex hulls at first basel 1. For each basel edge AB, 2. Search for switching points on L and R sides. Let them be N for A and M for B. 1. Choose between N and M to determine the next basel edge, then repeat. 2. Stop when reaching the upper common tangent. 3. The number of inCircle tests = number of delete edges, for this step. 47
Complexity analysis Get lower common tangent of L s and R s convex hulls at first basel 1. For each basel edge AB, 2. Search for switching points on L and R sides. Let them be N for A and M for B. 1. Choose between N and M to determine the next basel edge, then repeat. 2. Stop when reaching the upper common tangent. 3. Overall, the total number of inCircle tests for candidate selections in the entire process of finding cross edges will be no more than the total number of L or R Delaunay edges deleted. There are linear number of edges in the L and R Delaunay triangulations and no edge is deleted twice. Hence this step is linear-time and the entire process of finding cross edges is linear time. The whole divide-and-conqure algorithm takes O(n log n). 48
