Research
Research interests
I study the structural properties of geometric and graph-theoretic objects, and how those properties can be leveraged to design efficient algorithms and data structures.
Research areas
-
Geometric spanners and routing
Given a point set, graphs like the Delaunay triangulation and the Θ- and Yao-graph families approximate the complete Euclidean graph; the question is how well, and how cheaply you can navigate them. Much of this work pins down exact spanning and routing ratios — the directed Θ₆-graph, Θ₅, Yao-4, the parallelogram and arbitrary triangle Delaunay graphs — and designs online and local routing strategies that decide where to go next from almost no information: the current vertex, its neighbours and the destination, with no map and little or no memory.
-
Structure and algorithms in planar and near-planar graphs
Structural graph theory brought to bear on algorithmic questions: independence and basis numbers of 1-planar graphs, k-planar graphs without short cycles, product structure in planar graphs, layered versus row treewidth, vertex ranking, centred and linear chromatic numbers, and a range of problems on triangulations — connected dominating sets, 3-packings, polychromatic colourings with bounded discrepancy.
-
Geodesic geometry inside polygons
What happens to familiar geometric questions when distance is measured along shortest paths inside a simple polygon rather than across the plane. The smallest geodesic disk enclosing k points; disks that enclose many points; pairs of points such that every geodesic disk containing the pair contains a constant fraction of the set; the doubling dimension and perimeter of geodesically convex sets in fat polygons. Visibility belongs here too — k-visibility and k-crossing visibility regions, guarding and art gallery localization, self-approaching paths.
-
Pursuit–evasion and graph searching
How many pursuers does it take to catch an evader on a graph, and what structural property of the graph decides the answer? Cop number of 1-planar graphs and of graphs drawn on surfaces with crossings, cops and robbers under a bounded vertex cover, and the zombie variants — including lazy zombies and a survivor — where the pursuers move greedily rather than optimally.
-
Piercing, covering and Helly-type problems
How few points are needed to stab every member of a family of pairwise intersecting objects. Linear-time piercing of pairwise intersecting disks, then unit geodesic disks, geodesic disks and general convex shapes in the plane — and, on the covering side, improved bounds for plane covering paths.
-
Shortest paths in weighted domains
Path-finding when crossing a region costs something. Approximation algorithms for shortest paths in weighted triangular, square and hexagonal tessellations, Steiner-point methods on equilateral-triangle meshes, and shortest paths amid non-overlapping weighted disks — with attention to how well a discrete grid can approximate the true continuous path.
-
Networks on point sets
Trees, matchings and proximity structures built on points in the plane, usually under a geometric constraint that makes the classical algorithm fail. Bounded-angle minimum spanning trees and their average-angle variants, moving spanning trees over points in motion, restricted Steiner trees, noncrossing longest paths and cycles, separating path and tree systems, and closest-pair counts in vertical slabs.
Additional topics
- OnlineSearch Problems
- OnlineCompetitive Analysis
- StructuresAdaptive Data Structures
- StructuresSearch Trees & Dictionaries
- MeshesFlips in Triangulations
- DrawingGraph Drawing & Morphing
- DrawingBoundary Labelling
- IndustryMold Separation & Manufacturing
Searching on a line and in arrangements, competitive online algorithms, distribution-sensitive data structures, flips and morphs between triangulations, and the geometry of manufacturing.