Geometric Networks

The workshop will take place on Monday afternoon (June 22) and Tuesday afternoon (June 23), where the Monday afternoon will focus on stochastic aspects of networks, and the Tuesday afternoon on applied aspects. Each afternoon will feature a one-hour invited talk, as well as a number of shorter contributed talks.


14:00Invited talk Gabor Lugosi (Pompeu Fabra University)
Connectivity properties of random bluetooth networks [+]

Abstract: Consider a graph whose vertices represent n uniform random points in the unit square. One may form a random geometric graph by connecting two points by an edge if the distance of the points is at most r. Let c be a positive integer. We form a subgraph of the random geometric graph by selecting, at random, c vertices among the neighbors of any given vertex, and keeping only the edges joining the vertex to the selected neighbors. We present various results about connectivity properties of such graphs. Joint work with Nicolas Broutin and Luc Devroye.

15:00Nicholas Broutin (INRIA Paris-Rocquencourt)
Efficiently navigating a random Delaunay triangulation [+]

Abstract: Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant competitiveness which follows vertex adjacencies in the Delaunay triangulation. We call this strategy cone walk. We prove bounds on the complexity of this walk for the case where the points of the Delaunay triangulation are distributed uniformly in a smooth convex domain of unit area.

16:00Joe Mitchell (SUNY Stony Brook)
Geometric network optimization in the face of uncertainty [+]

Abstract: Optimization problems abound in geometric network applications. Many of these problems are NP-hard but have good approximation algorithms that exploit geometric structure. We consider problems in which there is uncertainty in the input data. There may be uncertainty, for example, in the input set S of vertices of a geometric graph; we may not know exactly which subset, V ⊆ S, of points from S are actually present, or we might, more generally, have a spatial probability distribution for each point pi∈ S. Additionally, the edges that interconnect S may be described stochastically, with edges that may or may not exist or whose lengths are uncertain, e.g., because of the presence of random obstacles. We examine some models of geometric network optimization in the face of uncertainty, pose some open problems, and discuss some results (hardness and approximation) in some of these models.

16:30Matya Katz (Ben-Gurion University of the Negev)
Batched point location in SINR Diagrams via algebraic tools [+]

Abstract: The SINR model for the quality of wireless connections has been the subject of extensive recent study. It attempts to predict whether a particular transmitter is heard at a specific location, in a setting consisting of n simultaneous transmitters and background noise. The SINR model gives rise to a natural geometric object, the SINR diagram, which partitions the space into n regions where each of the transmitters can be heard and the remaining space where no transmitter can be heard.

Efficient point location in the SINR diagram, i.e., being able to build a data structure that facilitates determining, for a query point, whether any transmitter is heard there, and if so, which one, has been recently investigated in several papers. These planar data structures are constructed in time at least quadratic in n and support logarithmic-time approximate queries. Moreover, the performance of some of the proposed structures depends strongly not only on the number n of transmitters and on the approximation parameter eps, but also on some geometric parameters that cannot be bounded a priori as a function of n or eps.

We address the question of batched point location queries, i.e., answering many queries simultaneously. Specifically, in one dimension, we can answer n queries exactly in amortized polylogarithmic time per query, while in the plane we can do it approximately. These results can handle arbitrary power assignments to the transmitters. Moreover, the amortized query time in these results depends only on n and eps. Finally, these results demonstrate the (so far underutilized) power of combining algebraic tools with those of computational geometry and other fields. Based on joint work with Boris Aronov.

17:00Kevin Buchin (TU Eindhoven)
Interference minimization in asymmetric sensor networks [+]

Abstract: A fundamental problem in wireless sensor networks is to connect a given set of sensors while minimizing the receiver interference. This is modeled as follows: each sensor node corresponds to a point in Rd and each transmission range corresponds to a ball. The receiver interference of a sensor node is defined as the number of transmission ranges it lies in. Our goal is to choose transmission radii that minimize the maximum interference while maintaining a strongly connected asymmetric communication graph. For the two-dimensional case, we show that it is NP-complete to decide whether one can achieve a receiver interference of at most 5. In the one-dimensional case, we prove that there are optimal solutions with nontrivial structural properties. These properties can be exploited to obtain an exact algorithm that runs in quasi-polynomial time. This generalizes a result by Tan et al. to the asymmetric case.

14:00Invited talk Roger Wattenhofer (ETH Zürich)
Wireless networks: Do not disturb my circles [+]

Abstract: Is geometry the key to a deeper understanding of wireless networks? In my talk I will present a few exciting research questions that I learned when studying wireless networks: Can we derive the geometry of a network merely by logging communication? Can we improve the capacity of a network by solving geometric optimization problems? Can we model a wireless network by geometry -- or should we disturb the circles?

15:00Lilach Chaitman (Ben-Gurion University of the Negev)
On the minimum-cost range assignment problem [+]

Abstract: We study the problem of assigning transmission ranges to radio stations in the plane such that any pair of stations can communicate within h hops and the cost of the network is minimized. The cost of transmitting in a range r is proportional to ralpha, where alpha ≥ 1. We consider two settings of this problem: collinear station locations and arbitrary locations.

For the case of collinear stations, we introduce the pioneer polynomial-time exact algorithm for any alpha ≥ 1 and constant h, and thus conclude that the 1D version of the problem for constant h is in P. For an arbitrary h, not necessarily a constant, and alpha=1, we propose a 1.5-approximation algorithm. This improves the approximation ratio of the best known algorithm which admits a 2-approximation [CFPPS00]. For h=n-1, i.e., the unbounded case, we propose a new approach that achieves an exact O(n2)-time algorithm. This improves the running time of the best known algorithm [DGN07] by a factor of n. Moreover, we show that this new technique can be utilized for achieving a polynomial-time algorithm for finding the minimum cost range assignment of collinear points whose induced communication graph is a t-spanner, for any t ≥ 1.

For the case of stations placed arbitrarily in the plane and alpha=1, we present a (3+epsilon)-approximation algorithm, for any epsilon>0 and a constant h. This improves the best known approximation ratio of 4(9h-2)/(sqrt[h]{2}-1), by [KP09]. Moreover, we show a (1.5+ epsilon)-approximation algorithm for a case where deviation of one hop (h+1 hops in total) is acceptable. For the unbounded case (h=n-1), the best known approximation ratio is 1.5 [ACPRS05]. We show a new approximation algorithm that breaks the 1.5 ratio.

16:00Subhash Suri (UC Santa Barbara)
Euclidean traveling salesman tours through stochastic neighborhoods [+]

Abstract: We consider the problem of planning a shortest tour through a collection of neighborhoods in the plane, where each neighborhood is a disk whose radius is an i.i.d. random variable drawn from a known probability distribution. This is a stochastic version of the classic traveling salesman problem with neighborhoods (TSPN). Planning such tours under uncertainty, a fundamental problem in its own right, is motivated by a number of applications including the following data gathering problem in sensor networks: a robotic data mule needs to collect data from n geographically distributed wireless sensor nodes whose communication range r is a random variable influenced by environmental factors. We propose a polynomial-time algorithm that achieves a factor O(loglog n) approximation of the expected length of an optimal tour. In data mule applications, the problem has an additional complexity: the radii of the disks are only revealed when the robot reaches the disk boundary (transmission success). For this online version of the stochastic TSPN, we achieve an approximation ratio of O(log n). In the special case, where the disks with their mean radii are disjoint, we achieve an O(1) approximation even for the online case.

16:30Andre van Renssen (National Institute of Informatics)
Competitive local routing with constraints [+]

Abstract: Let P be a set of n points in the plane and S a set of non-crossing line segments between vertices in P, called constraints. These constraints can be viewed as obstacles that block communication in the network. Two vertices are visible if the straight line segment connecting them does not properly intersect any constraints. The constrained thetam-graph is constructed by partitioning the plane around each vertex into m disjoint cones, each with aperture theta = 2pi/m, and adding an edge to the `closest' visible vertex in each cone. We consider how to route on the constrained theta6-graph. We first show that no deterministic 1-local routing algorithm is o(sqrt{n})-competitive on all pairs of vertices of the constrained theta6-graph. After that, we show how to route between any two visible vertices of the constrained theta6-graph using only 1-local information. Our routing algorithm guarantees that the returned path has length at most 2 times the Euclidean distance between the source and destination. To the best of our knowledge, this is the first local routing algorithm in the constrained setting with guarantees on the length of the returned path.

17:00Cyrille Gavoille (Université de Bordeaux)
An overview on compact routing [+]

Abstract: In this talk I present an overview on the field of compact routing. I give the main variants of the problems (labeled, name-independent, metric space routing, ...), followed by a state-of-the-art of the field which is declined for several families of graphs (from general to planar graphs). As illustration, I give also a simple stretch-3 compact routing scheme of general metrics. A list of main open questions is given.

17:30Open Problem Session

Invited speakers
We are happy to announce Gabor Lugosi (Pompeu Fabra University) and Roger Wattenhofer (ETH Zurich) as invited speakers.