December 2, 2003 Lecture 24: Combinatorial Geometry1Combinatorial GeometryPiotr IndykDecember 2, 2003 Lecture 24: Combinatorial Geometry2Previous Lecture• Algorithm for matching A in B:– Take any pair a,a’∈A, let r=||a-a’||– Find all pairs b,b’∈B such that ||b-b’||=r– For all such pairs• Compute t that transforms (a,a’) into (b,b’)• Check if t(A) ⊆ BDecember 2, 2003 Lecture 24: Combinatorial Geometry3Combinatorial Question• Given a set A of n points in the plane, what is the maximum number of p,p’∈Asuch that ||p-p’||=1 ?– Erdos’46: O(n3/2)– Jozsa, Szemeredi’73: o(n3/2)– Beck, Spencer’84: O(n1.44…)– Spencer, Szemeredi, Trotter’84: O(n4/3)– Szekely’96: O(n4/3), proof in 4 slidesDecember 2, 2003 Lecture 24: Combinatorial Geometry4Crossing Number• Crossing number of a graph G: smallest ksuch that G can be drawn on the plane with at most k edges crossing• Interested in bounds of the form k f(n,e)December 2, 2003 Lecture 24: Combinatorial Geometry5Simple Bound• We know that k e - 3n• Proof:– Assume G with k<e-3n– Then there is a graph with k-1 crossings and e-1 edges– …..– There is a graph with 0 crossings and e-kedges– But e-k 3n – a contradictionDecember 2, 2003 Lecture 24: Combinatorial Geometry6Bounds• The earlier lower bound is pretty weak. E.g., it lower bounds k by at most e• Complete graph has crossing number Ω(n4)• Need to “amplify” the boundDecember 2, 2003 Lecture 24: Combinatorial Geometry7Probabilistic Amplification• Given G, construct G’ by random sampling• Each node is included in G’ with probability p=4 n/e (assume e 4n)• The expected parameters n’,e’,k’ of G’ are:– E[n’]=pn– E[e’]=p2e– E[k’] p4kDecember 2, 2003 Lecture 24: Combinatorial Geometry8Proof• We know that k’+3n’-e’ 0• Thus E[k’+3n’-e’]=E[k’]+3E[n’]-E[e’] 0• We get:p4k + 3pn - p2e 0p3k pe – 3n = 4n-3n = nk e3/(43n2) = Ω(e3/n2) e=O( (kn2)1/3 ) [Leighton’83][Ajtai,Chvatal,Newborn,Szemeredi’82]December 2, 2003 Lecture 24: Combinatorial Geometry9Number of Unit Distances• Nodes = points = n• Multi-edges defined by arcs #unit distances• Keep one out of 4 edges, so we get a graph• # crossings 2 n2QEDDecember 2, 2003 Lecture 24: Combinatorial Geometry10Other Bounds• Number of incidences between n lines and n points = O(n4/3)• Given n points, the number of distinct distances between them is at least Ω(n4/5)December 2, 2003 Lecture 24: Combinatorial Geometry11Improved Algorithm• Take the pair a,a’∈A with the lowest multiplicity in B; let r=||a-a’||• Find all pairs b,b’∈B such that ||b-b’||=r• For all such pairs– Compute t that transforms (a,a’) into (b,b’)– Check if t(A) ⊆ BDecember 2, 2003 Lecture 24: Combinatorial Geometry12Analysis• For a distance t, let mA(t) be the multiplicity of t in A•tmB(t) n2• There are at least n4/5different t’s such that mA(t) 1• So, if there is a match, there must exist tsuch that mA(t) 1 and mB(t) n6/5• Algorithm has running time O(n11/5)December 2, 2003 Lecture 24: Combinatorial Geometry13Higher Dimensions• What is the number of unit distances between n points in R4?• At least n2/4:– Let A={(x,y,z,u): x2+y2=1, z=u=0}– Let B={(x,y,z,u): z2+u2=1, x=y=0}– For any a∈A, b∈B, we have ||a-b||2=1– Take n/2 points from A and n/2 points from