The (maximum receiver-centric) interference of a geometric graph (von (2005)) is studied. It is shown that, with high probability, the following results hold for a set, V, of n points independently and uniformly distributed in the unit d-cube, for constant dimension d: (1) there exists a connected graph with vertex set V that has interference O((log n)^ 1 3 ); (2) no connected graph with vertex set V has interference o((log n)^ 1 4 ); and (3) the minimum spanning tree of @math has interference Theta(( n)^ 1 2 ).
log suggests that point sets with very high interference are unlikely to occur in practice. This intuition is born out by the results of Kranakis al @cite_7 , who show that high interference is unlikely to occur in random point sets in one dimension: Note that, in this one-dimensional case, the minimum spanning tree, @math , is simply a path that connects the points of @math in order, from left to right. Taken together, Part 1 of Theorems and generalize sqrtlogn to arbitrary constant dimensions @math .
@cite_7
1942343061
(MATH) Let P be a set of n points in @math k (P) denote the minimum over all k-flats @math of max peP Dist(p, ). We present an algorithm that computes, for any 0 k (P) from each point of P. The running time of the algorithm is dnO(k e5log(1 e)). The crucial step in obtaining this algorithm is a structural result that says that there is a near-optimal flat that lies in an affine subspace spanned by a small subset of points in P. The size of this "core-set" depends on k and e but is independent of the dimension.This approach also extends to the case where we want to find a k-flat that is close to a prescribed fraction of the entire point set, and to the case where we want to find j flats, each of dimension k, that are close to the point set. No efficient approximation schemes were known for these problems in high-dimensions, when k>1 or j>1. The problem of finding a minimum spanning tree connecting n points in a k-dimensional space is discussed under three common distance metrics -- Euclidean, rectilinear, and @math . By employing a subroutine that solves the post office problem, we show that, for fixed k @math 3, such a minimum spanning tree can be found in time O( @math ), where a(k) = @math . The bound can be improved to O( @math ) for points in the 3-dimensional Euclidean space. We also obtain o( @math ) algorithms for finding a farthest pair in a set of n points and for other related problems. Given @math wireless transceivers located in a plane, a fundamental problem in wireless communications is to construct a strongly connected digraph on them such that the constituent links can be scheduled in fewest possible time slots, assuming the SINR model of interference. In this paper, we provide an algorithm that connects an arbitrary point set in @math slots, improving on the previous best bound of @math due to Moscibroda. This is complemented with a super-constant lower bound on our approach to connectivity. An important feature is that the algorithms allow for bi-directional (half-duplex) communication. One implication of this result is an improved bound of @math on the worst-case capacity of wireless networks, matching the best bound known for the extensively studied average-case. We explore the utility of oblivious power assignments, and show that essentially all such assignments result in a worst case bound of @math slots for connectivity. This rules out a recent claim of a @math bound using oblivious power. On the other hand, using our result we show that @math slots suffice, where @math is the ratio between the largest and the smallest links in a minimum spanning tree of the points. Our results extend to the related problem of minimum latency aggregation scheduling, where we show that aggregation scheduling with @math latency is possible, improving upon the previous best known latency of @math . We also initiate the study of network design problems in the SINR model beyond strong connectivity, obtaining similar bounds for biconnected and @math -edge connected structures. A dynamic geometric data stream is a sequence of m ADD REMOVE operations of points from a discrete geometric space 1,…, Δ d ?. ADD (p) inserts a point p from 1,…, Δ d into the current point set P, REMOVE(p) deletes p from P. We develop low-storage data structures to (i) maintain e-nets and e-approximations of range spaces of P with small VC-dimension and (ii) maintain a (1 + e)-approximation of the weight of the Euclidean minimum spanning tree of P. Our data structure for e-nets uses bits of memory and returns with probability 1 – δ a set of points that is an e-net for an arbitrary fixed finite range space with VC-dimension . Our data structure for e-approximations uses bits of memory and returns with probability 1 – δ a set of points that is an e-approximation for an arbitrary fixed finite range space with VC-dimension . The data structure for the approximation of the weight of a Euclidean minimum spanning tree uses O(log(1 δ)(log Δ e)O(d)) space and is correct with probability at least 1 – δ. Our results are based on a new data structure that maintains a set of elements chosen (almost) uniformly at random from P.