Computational Geometry Laboratory

Current Projects

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.

Stephane Durocher, Debajyoti Mondal, Maxime Peabody, Matthew Skala, Mohammad Abdul Wahid

David Kirkpatrick, Lata Narayanan, Prosenjit Bose, Paz Carmi, Jean-Lou de Carufel, Alireza Haghnegahdar, Majid Khabbazian, Fabian Kuhn, Perouz Taslakian

SOFSEM 2015, TON 2014, SWAT 2014, SIROCCO 2012, Distributed Computing 2012, Wireless Networks 2010, PODC 2009, ICDCN 2008

 

When wireless nodes are represented by points in Euclidean space, networks edges are defined by a geometric proximity graph, and the distance between two nodes is measured by the number of network hops on a shortest path connecting them, the resulting facility location problems are set neither solely in Euclidean space nor on a graph. Although similar to problems of facility location in both settings, existing solutions do not necessarily apply to this new combination of graph-theoretic and geometric constraints.

Unit disc graphs are proximity graphs that are frequently used to model wireless networks. We consider the k-centre problem on unit disc graphs: given a set of points P in the plane, find a set F of k points in the plane that minimizes the maximum graph distance from any vertex in P to the nearest vertex in F in the unit disc graph induced by P ∪ F. We describe exact and approximate polynomial-time solutions to this problem for any fixed k and show that the problem is NP-hard when k is an arbitrary input parameter.

Stephane Durocher, Saeed Mehrabi

Krishnam Raju Jampani, Anna Lubiw, Lata Narayanan,

CGTA 2011, DIAML-POMC 2008

 

Given a list A[1:n] of n items, we consider the problem of constructing a (typically linear-sapce) 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).

Stephane Durocher, Jason Morrison, Matthew Skala

Timothy Chan, Meng He, Kasper Green Larsen, Ian Munro, Patrick Nicholson, Rahul Shah, Sharma Thankachan, Bryan Wilkinson

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

 

Debajyoti Mondal is a Ph.D. student 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.

Stephane Durocher, Saeed Mehrabi, Debajyoti Mondal

Stefan Felsner, Ellen Gethner, Rahnuma Islam Nishat, Md. Saidur Rahman, Sue Whitesides

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

 

Saeed Mehrabi is a Ph.D. 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.

Stephane Durocher, Omrit Filtser, Bob Fraser, Ali Mehrabi, Saeed Mehrabi

COCOA 2014, IWOCA 2014, LATIN 2014, MFCS 2013, COCOON 2012

 

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.

Stephane Durocher, Bob Fraser, Alexandre Leblanc, Jason Morrison, Matthew Skala

CCCG 2014, IJCGA 2013, ISAAC 2012