שחר סמורודינסקי

We present new results on 2- and 3-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2- and 3-hop spanners for many geometric intersection graphs in Rd. For example, we show that the intersection graph of n balls in Rd admits a 2-hop spanner of size O∗ (n3/2 - 1/2(2⌈d/2⌉+1)) and the intersection graph of n fat axis-parallel boxes in Rd admits a 2-hop spanner of size O(n logd+1 n). Furthermore, we show that the intersection graph of general semi-algebraic objects in Rd admits a 3-hop spanner of size O∗ (n3/2 - 1/2(2D-1)), where D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in R3), we provide a lower bound of Ω(n 4/3). For 3-hop and axis-parallel boxes in Rd, we provide the upper bound O(n logd-1 n) and lower bound Ω (n(log n/log log n)d-2).