Proximity Greedy triangulation star of spokes Star of spokes greedy triangulation The simple greedy triangulation had two phases 1 Generation and presort of possible edges O N2 log N time 2 Determining if each possible edge belongs in the triangulation O N3 time The star of spokes algorithm reduces the second phase to O N2 log N overall by processing each of the O N2 possible edges in O log N time Here processing means to test a possible edge for intersection with edges already in the triangulation We will see a way to perform that test in O log N time That time suggests a search data structure of some kind Proximity Greedy triangulation star of spokes Star of spokes Suppose the current possible edge is edge p1pi Consider a set of edges connecting p1 to every other point in S These edges called spokes are not in the triangulation there are defined for the search structure The point p1 and the spokes are together referred to as STAR p1 the star of spokes of p1 The spokes are ordered say counterclockwise and they subdivide the 2 angle around p1 into N 1 angular intervals called sectors pi p1 Proximity Greedy triangulation star of spokes Triangulation edges and sectors Suppose edge pjpk is already part of the triangulation i e a triangulation edge It spans a set of consecutive sectors relative to p1 and the same is true for any pl S pj pk Observe that because triangulation edges run from point to point and points define sectors edges always entirely span sectors rather than partially spanning them Note also that triangulation edges do not intersect each other by definition so the triangulation edges present in each sector of STAR pl pl S can be ordered from pl outwards pi pj p1 pk Proximity Greedy triangulation star of spokes What to check Recall that edge p1pi is the possible triangulation edge that is being tested for intersection with other triangulation edges Assume that in STAR p1 point pi is located in sector pkp1pj To determine whether edge p1pi can be added to the triangulation it must be determined if edge p1pi intersects any other triangulation edge It is sufficient to check those triangulation edges that span sector pkp1pj and if there are 1 such edges it is sufficient to check the one closest to p1 in that sector Conceptually if pi is closer to p1 than the closest spanning edge edge p1pi can be added if not it cannot For each sector of STAR pl for every pl S the closest triangulation edge must be maintained Preparata calls this a special case of planar point location pi pj p1 pk Proximity Greedy triangulation star of spokes Example situation The figure shows STAR p1 in some typical situation The heavy edges are triangulation edges and the lighter edges are spokes A possible triangulation edge p1pi can be added iff pi is in the shaded area Proximity Greedy triangulation star of spokes Search data structure The data structure to store the spanning edge for each sector in STAR pl for pl S must support two operations 1 Query to determine if a possible triangulation edge intersects a spanning triangulation edge 2 Insertion of new triangulation edges The second operation indicates that a dynamic data structure is needed We would like the operations to execute in O log N time Because each insertion involves a sequence of consecutive spanned sectors a segment tree is suggested Proximity Greedy triangulation star of spokes Sectors of STAR pl The sectors of STAR pl can be numbered in counterclockwise order from 1 to N 1 3 1 2 4 2 3 4 5 pl 5 sector 9 9 6 6 1 7 7 8 8 Point in CCW sequence Proximity Greedy triangulation star of spokes Segment tree for STAR pl The sectors of STAR pl are represented as the N 1 leaves of a segment tree referred to as Tl defined for interval 1 N 1 10 1 5 5 10 1 3 3 5 5 7 7 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 1 2 3 4 5 6 7 8 10 8 9 9 10 8 9 Each node v of Tl has a field e v that stores an edge Field e v identifies the triangulation edge closest to to pl in the sector s that correspond to the node v Proximity Greedy triangulation star of spokes Insertion When an edge pipj arbitrary not pipj from earlier figure is to be added to the triangulation it is inserted into the segment tree Tl representing STAR pl for every pl S l i j During a single insertion at each allocation node v in the segment tree Tl edge pipj is tested against the edge identified by e v If edge pipj is closer e v is updated to identify edge pipj No ambiguity about closest is possible because 1 Triangulation edges do not intersect 2 An edge is only allocated to a node v if it spans all the sectors for that node 1 2 not possible Test and update of e v take constant time at each node Insertion into the segment tree will visit O log N nodes so the insertion time is O log N Proximity Greedy triangulation star of spokes Query To test if edge pipj arbitrary not pipj from earlier figure intersects any edge of the triangulation search segment tree Tl representing STAR pl with the number of the sector contain pj The search will trace a single path of nodes in Ti from root to leaf At each node v on the path test edge pipj for intersection with e v If an intersection is found stop If the search reaches a leaf without finding any intersections accept edge pipj for the triangulation add it to every segment tree A segment tree has depth O log N so there are O log N nodes visited during the query The intersection test at each one require O 1 time The query requires O log N time pj pi pj Proximity Greedy triangulation star of spokes Star of spokes greedy triangulation analysis Time O N2 log N O N2 log N for presort of all possible edges O N2 edges O log N processing for each Storage O N2 O N storage for the segment tree for each of N points Proximity Constrained triangulation Problem definition CONSTRAINED TRIANGULATION INSTANCE Set S p1 p2 pN of N points in the plane and set E pi pj of nonintersecting edges on S QUESTION Join the points in S with nonintersecting straight line segments so that every region internal to the convex hull of S is a triangle and every edge of E is in the triangulation For this problem optimization e g edge length minimization is not required A greedy method will work with the edges in E put into the triangulation initially but performance is not optimum Delaunay triangulation is not easily adapted Proximity Constrained triangulation Assumptions Given S and E assume 1 We will triangulate not S but instead the …
View Full Document