Stephane Durocher

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:
- the node from which the message originated,
- which of its neighbours last forwarded the message, and
- the subgraph corresponding to all network nodes within k hops of itself, for some value of k.

- 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.

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:
- minimum-segment drawings of planar graphs,
- plane 3-trees,
- thickness and colourability,
- pairwise compatibility graphs, and
- point-set embeddings.

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:
- sliding cameras (art galleries with line segment guards), and
- partitions with minimum stabbing number.

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:
- nonparametric simplication for piecewise linear curves, and
- measures of data depth defined in terms of combinatorial geometry.

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