1、Joseph S. B. MitchellStony Brook University n n log n n210 10 10 210 104 220 106220 106 20 220 2 107 240 1012InteractiveProcessing n log n algorithms n algorithmsn = 1000 yes ?n = 1000000 ? noFunction T(n) is O(f(n) if there exists a constant C such that , for sufficiently large n, T(n) 0c is left o
2、f abO(n3)O(n)spqrO(n2)O(n)prqCaution! Numerical errors require care to avoid crash/infinite loop!Applet by SnoeyinkpqrJarvis MarchKey observation:Output-sensitive!O(n) per steph stepsTotal: O(nh)O(n log n)O(n)O(n)Demo appletvlowestCH so farJoseph S. B. MitchellStony Brook University(since CH vertice
3、s are subset of maximal points)O(n log n)O(n)O(n)Demo appletvlowestCH so farvlowestCH so farSleftSrightTime:T(n) 2T(n/2) + O(n)T(n) = O(n log n)Time O(n)Time O(n)Time 2T(n/2)Demo appletQhull websiteQhull, Brad Barber (used within MATLAB)abcSBAWorst-case: O(n2 )Avg: O(n)Discard points in abcc = point
4、 furthest from abWorks well in higher dimensions too!Joseph S. B. MitchellStony Brook UniversityPoint location test: O(log n)Binary search: O(log n)vi+1eBackwards Analysis:vj was just rebucketed iff the last point inserted was one of the 2 endpoints of the (current) conflict edge, e, for vjvjh = out
5、put sizeSo, O(n log h) is BEST POSSIBLE, as function of n and h != O(n log h)= O( h (n/h) log h) = O(n log h)vO(n ( log (221 ) + log (222 ) + log (223 ) + log (22 log (log (h) )= O(n (21 + 22 + 23 + + 2log (log (h) )= O(n (2 log h) = O(n log h)v12nviTime: O(n), since O(1) per insertionvbvb+1vt-1vtvi
6、vtvbvt-1vb+1Simplicityhelps!mergeh= O(n)Qhull websiteappletJoseph S. B. MitchellStony Brook UniversityMay also want to insert/delete in S, or allow objects of S to move.Nave: O(n2)CG: O(n log n) DETECT, O(k+n log n) REPORTLower Bound to DETECT: (n log n) , from ELEMENT UNIQUENESSElement UniquenessIn
7、put: x1, x2, ,xn Are they distinct? (yes/no)(n log n)abcLeft( a, b, c ) = TRUE ab ac 0c is left of abLO(n log n)LO(log n)LabeFind segs a and b above/below e in SLS. Insert e into SLS. Test(a,e), Test(b,e) and insert crossings (if any) in EQabeLFind segs a and b above/below e in SLS. Delete e from SL
8、S. Test(a,b), and insert crossing (if any) in EQabLefO(log n)O(log n)Exchange e, f in SLS. Test(a,f), Test(b,e) and insert crossings (if any) in EQk = # crossings = output sizeevents (and at most 2n endpoint events)Better bounds on size of EQ: O(n log2 n) Pach and Sharir(Complex)LAll crossings happe
9、n when L hits a vertical segment, si ; just locate (O( log n) the endpoint and walk along vertical segment in SLS to report all ki horizontal segments crossed along sif0f1ee4,0v1v0Pop quiz.-How to enumerate all edges of a face?-How to enumerate all edges incident on a node?es twinv2v7v6v5v3v4e0,1 Ev
10、ery edge e is struct: e.org, e.dest: pointer to origin and dest vertices. e.face is face on left of edge e.twin is the same edge, oriented the other direction. Each Face has a pointer to one edge of that face. Each vertex has pointer to one edge away from that vertex.Ack: R. Pless Find “smallest” (t
11、ightest fitting) pair of bounding boxesTriangulating a monotone polygon, introductionThe algorithm to triangulate a monotone polygondepends on its monotonicity.Developed in 1978 by Garey, Johnson, Preparata, and Tarjan,it is described in both Preparata pp. 239-241 (1985) andLaszlo pp. 128-135 (1996)
12、.The former uses y-monotone polygons, the latter uses x-monotone.InitializationSort the N vertices of monotone polygon P in order by decreasingy coordinate. (Here N is the number of vertices of P, not S.)The sort can be done in O(N) time, not O(N log N),by merging the two monotone chains of P.Let u1
13、, u2, , uN be the sorted sequence of vertices,so y(u1) y(u2) y(uN).Because of the regularization process and the monotonicity of P,for every ui 1 i N there exists uj 1 y(v2) y(vi).2. If i 3, angle vjvj+1vj+2 for 1 j i - 2.AlgorithmBy “adjacent” we mean connected by an edge in P.Recall that v1 is the
14、 bottom of the stack, vi is the top.1.Push u1 and u2 on the stack.2. j = 3 /* j is index of current vertex */3. u = uj4. Case (i): u is adjacent to v1 but not vi.add diagonals uv2, uv3, , uvi.pop vi, vi-1, , v1 from stack.push vi, u on stack.Case (ii): u is adjacent to vi but not v1.while i 1 and an
15、gle uvivi-1 add diagonal uvi-1pop vi from stackendwhilepush uCase (iii): u adjacent to both v1 and vi.add diagonals uv2, uv3, , uvi-1.exit5. j = j + 1Go to step 3.Algorithm casesCase (i): u is adjacent to v1 but not vi.v1v2v3v4 = vi top of stackuCase (ii): u is adjacent to vi but not v1.v1v2v3v4v5 =
16、 vi top of stackuCase (iii): u adjacent to both v1 and vi.v1v2v3v4 = vi top of stackuExample, 1v11, initialv2uv12, Case (ii)v2uv3v13, Case (ii)v2v3uv44, Case (i)v2uv1Example, 25, Case (ii)v2uv16, Case (ii)v2uv1v37, Case (ii)v2uv1v3v48, Case (ii)v2uv1v3Example, 39, Case (iii)10, finalProof of correct
17、nessThe correctness of the algorithm depends on the fact that all theadded diagonals lie inside the polygon P.For details, see Preparata pp. 240-241, or Laszlo pp. 134-135.Analysis of triangulating a monotone polygonThe initial sort (merge) requires O(N) time.Each of the N vertices is visited and pl
18、aced on the stackexactly once, except when the while fails in case (ii).This happens at most once per vertex,so that time can be charged to the current vertex. The algorithm requires O(N) time to triangulate a monotonepolygon, where N is the number of vertices of the polygon. Application: Nearest-neighbor queries (by point location in the diagram).The bisector between two points is a line.Beach linebreakpointP1P3P1P2P1P3P3P1P2P1P1P3P22n-1P1 P1, P2, P1P1P2Beach lineFalse AlarmVertex event Add new triples to tree.space O(n).dcPPbaPPbaPPdcPPyxPPdcPPLR.zxPPzyPPzyPPzxPPyzPP
