A local routing algorithm makes a sequence of distributed forwarding decisions, each of which is made using only local information. Specifically, in addition to knowing the node for which a message is destined, an intermediate node might also know:

1. the node from which the message originated,
2. which of its neighbours last forwarded the message, and
3. the subgraph corresponding to all network nodes within k hops of itself, for some value of k.

We examine theoretical bounds on the locality of routing. Our objective is to determine which of these parameters are necessary and/or sufficient to permit local routing as k varies on a network modelled by a connected undirected graph. Our results include:

• showing that no k-local routing algorithm succeeds on unit ball graphs for any fixed k when nodes are location-aware,
• establishing tight bounds on k for the feasibility of deterministic k-local routing under various combinations of these parameters, and
• establishing tight bounds on the dilation (the worst-case ratio of actual route length to shortest path length) for k-local routing algorithms.

David Kirkpatrick, Lata Narayanan, Prosenjit Bose, Paz Carmi

Wireless Networks 2010, PODC 2009, ICDCN 2008

This project seeks to identify optimal data structures for storage and retrieval of spatial data. Specifically, we consider various problems on digital elevation models (terrains) of the ocean floor, including:

• Given a set of piecewise-linear contour lines, define a hierarchical set of one-sided approximations to the contours to efficiently answer queries that determine whether an input piecewise-linear trajectory at a constant depth intersects the terrain.
• Construct an optimal adaptive range query data structure for box queries on a given set of points in the plane.
• Given a set of unit discs, a set of points covered by these discs, and an integer k, it is NP-hard to determine whether there exists a subset of at most k discs that covers the points. We consider geometric constraints under which the problem is solvable in polynomial time, and describe efficient algorithms for these cases.

See the project web page for additional information.

Alex López-Ortiz, Ian Munro, Bob Fraser, Alejandro Salinger, Reza Dorrigiv, Arash Farzan, Matthew Skala, Diego Arroyuelo, Francisco Claude, Meng He, Patrick Nicholson

TCS 2011, DMAA 2010, ISAAC 2009, ISAAC 2009, WADS 2009

A dense network can be modelled by a continuous region, where each node corresponds to a point in the region. Within this model, a routing policy assigns a continuous path to each origin-destination pair. A natural objective in selecting a routing policy is to minimize the load passing through any single node. While the average load is minimized by straight-line routing, such a routing policy distributes the load non-uniformly, resulting in higher load near the centre of the region. The significance of this problem was highlighted in a recent paper by Karp and Papadimitriou (MOBIHOC 2007). We consider various one-turn rectilinear routing policies in rectangular regions, resulting in a 33% reduction in the maximum load. Our policies are simple to implement, being both local and memoryless. We provide a lower bound that shows that no one-turn rectilinear routing policy can reduce the maximum load by more than 39%. Open questions include identifying policies that reduce the maximum load on more general convex regions.

Lata Narayanan, Evangelos Kranakis, Danny Krizanc

JOIN 2009, TAMC 2008

The traditional problems of facility location are set in a static setting; client positions are fixed and a single location is selected for each facility. Within the last few years, partly motivated by the applicability of mobile computing to the wireless telecommunications industry, these questions have been posed in the mobile setting. Given a set of clients, each of which follows a continuous trajectory over time, the location of a mobile facility is specified as a function of the client positions. The suitability of a mobile facility is determined not only by the quality of its optimization of the objective function but also by the maximum velocity and continuity of its motion. These additional factors often require the optimal location to be approximated, leading to new approximation strategies quite different from previous static approximations.

This research presents a variety of challenges including identifying strategies for defining motion for a set of facilities, deriving bounds on the continuity and maximum velocity of the motion and on the quality of approximation for a given strategy, deriving combinatorial bounds on the complexity of the corresponding motion, and developing efficient kinetic algorithms for maintaining the corresponding positions for a set of mobile facilities as a function of client motion.

Specific mobile facility location problems considered include:

• the Euclidean 1-centre (centre of the smallest enclosing circle) in the plane,
• Euclidean 2-centres in the plane,
• a Euclidean 1-median (Weber point) in the plane, and
• a 1-centre and 2-centres on trees.

See this Java applet for a graphical implementation of some of these results.

David Kirkpatrick, Christophe Paul

CGTA 2011, DAM 2009, CGTA 2009, IJCGA 2008, ISAAC 2007, IJCGA 2006, Ph.D. 2006, FWCG 2005, CCCG 2005, CCCG 2004, CCCG 2003

Array Range Query

Overview

Collaborators

Publications

Range scanners capture sample data points from an input polygonal or polyhedral surface such as a room or building. We examine the two-dimensional problem of reconstructing the original polygon as a function of the sample data and their associated geometric constraints. We consider various combinations of geometric constraints, including knowledge of edge orientation, interior/exterior, simplicity, connectivity, orthogonality, and monotonicity. A solution may not exist, may be unique, or multiple solutions may be possible. The problem is solvable in polynomial time under some combinations of geometric constraints while it is NP-hard under others.

David Kirkpatrick, Therese Biedl, Jack Snoeyink

TCS 2011, ISAAC 2009, FWCG 2008, CCCG 2002, M.Sc. 1999, PIMS 1999

The rectilinear crossing number of the complete graph is a well-known problem in geometric graph theory for which we improved on long-standing upper and lower bounds. The rectilinear crossing number of a graph G is the fewest number of edge crossings attainable over all straight-edge drawings of G in the plane. We describe new drawings of the complete graph that had the fewest number of edge crossings known to date. Since its publication, our work has generated considerable new activity in the area, resulting in dozens of further improvements, some of which employ our techniques to further improve bounds which, until our paper, had remained unchanged for over thirty years.

Alex Brodsky, Ellen Gethner

DM 2003, EJC 2001