Research Projects
Below are descriptions of a selection of my current and past research projects. I have not included unpublished manuscripts, work in progress, or smaller research projects. See my publications for a complete list.

My current research is funded by an NSERC Discovery Grant, an NSERC Engage Grant with Cogmation Robotics, two grants from the University Research Grants Program at the University of Manitoba, and a University of Manitoba Start-Up Research Grant.

See this page for a list of current graduate students and postdoctoral fellows currently working with me.

For additional information on my research projects, visit the the Computational Geometry Laboratory's website.

Current Projects
Local Routing in Wireless Networks
Overview
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:

Collaborators
David Kirkpatrick, Lata Narayanan, Prosenjit Bose, Paz Carmi, Jean-Lou de Carufel, Alireza Haghnegahdar, Majid Khabbazian, Fabian Kuhn, Debajyoti Mondal, Maxime Peabody, Matthew Skala, Perouz Taslakian, Mohammad Abdul Wahid

Publications
SOFSEM 2015, TON 2014, SWAT 2014, SIROCCO 2012, Distributed Computing 2012, Wireless Networks 2010, PODC 2009, ICDCN 2008
 
Array Range Query
Overview
Given a list A[1:n] of n items, we consider the problem of constructing a (typically linear-space) data structure that efficiently answers subsequent range frequency queries on A. Each query consists of an input pair of indices (i, j) for which a particular statistic of A[i:j] must be returned (e.g., a mode, minimum, least-frequent element, minority, or majority).

Collaborators
Timothy Chan, Meng He, Kasper Green Larsen, Jason Morrison, Ian Munro, Patrick Nicholson, Rahul Shah, Matthew Skala, Sharma Thankachan, Bryan Wilkinson

Publications
Algorithmica 2014, Algorithmica 2014, TOCS 2014, CCCG 2014, SPIRE 2013, MFCS 2013, Munro Festschrift 2013, ToCS 2013, InfoComp 2013, SWAT 2012, STACS 2012, ICALP 2011
 
Graph Drawing
Overview
Debajyoti Mondal is a Ph.D. student with whom I work in the Computational Geometry Laboratory working on problems in graph drawing, including results on:

Collaborators
Ellen Gethner, Stefan Felsner, Saeed Mehrabi, Debajyoti Mondal, Rahnuma Islam Nishat, Md. Saidur Rahman, Sue Whitesides

Publications
SIDMA 2015, GD 2014, GD 2014, CCCG 2014, LATIN 2014, GD 2013, JGAA 2013, WADS 2013, WG 2013, WALCOM 2013, WALCOM 2012, COCOA 2012, GD 2011, CCCG 2011
 
Geometric Optimization
Overview
Saeed Mehrabi is a Ph.D. student with whom I work in the Computational Geometry Laboratory working on algorithms for exact and approximate solutions to problems in geometric optimization, including results on:

Collaborators
Omrit Filtser, Bob Fraser, Ali Mehrabi, Saeed Mehrabi

Publications
COCOA 2014, IWOCA 2014, LATIN 2014, MFCS 2013, COCOON 2012
 
Data Approximation
Overview
This project involves research in simplifying and estimating geometric point data, including work on:

Collaborators
Bob Fraser, Alexandre Leblanc, Jason Morrison, Matthew Skala

Publications
CCCG 2014, IJCGA 2013, ISAAC 2012
 
Optimal Geometric Data Structures
Overview
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.

Links
See the project web page for additional information.

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

Publications
JOCG 2014, TCS 2011, DMAA 2010, ISAAC 2009, ISAAC 2009, WADS 2009
Past Projects
Polygon Reconstruction
Overview
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.

Collaborators
David Kirkpatrick, Therese Biedl, Jack Snoeyink

Publications
TCS 2011, ISAAC 2009, FWCG 2008, CCCG 2002, M.Sc. 1999, PIMS 1999
 
Mobile Facility Location
Overview
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.

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

Collaborators
David Kirkpatrick, Christophe Paul

Publications
CGTA 2011, DAM 2009, CGTA 2009, IJCGA 2008, ISAAC 2007, IJCGA 2006, Ph.D. 2006, FWCG 2005, CCCG 2005, CCCG 2004, CCCG 2003
 
Load-Balanced Routing in Dense Wireless Networks
Overview
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.

Collaborators
Lata Narayanan, Evangelos Kranakis, Danny Krizanc

Publications
JOIN 2009, TAMC 2008
 
Rectilinear Crossing Number of the Complete Graph
Overview
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.

Collaborators
Alex Brodsky, Ellen Gethner

Publications
DM 2003, EJC 2001