Publications
indicates that
a conference version of the paper appears below.
indicates that
a journal version of the paper appears above.
The journal version is more recent
(and usually more complete).
My current research is funded by
the NSERC Discovery Grant program,
the NSERC Accelerator Grant program,
the NSERC Engage Grant program,
the University Research Grants Program at the University of Manitoba,
and a University of Manitoba Start-Up Research Grant.
Here is (an approximation of)
my
co-author graph,
my DBLP page, and my Google Scholar page.
A list of my current and past students can be found
here.
Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set.
33(1&2):25-41. 2023.
(
pdf)
(
doi)
(
arXiv:2108.12464)
On the Restricted k-Steiner Tree Problem.
44:2893-2918. 2022.
(
doi)
Robustness and Asymptotics of the Projection Median.
181. 18 pages. 2021.
(
doi)
Computing the k-Visibility Region of a Point in a Polygon.
64:1292-1306. 2020.
(
doi)
Local Routing in Convex Subdivisions.
30(1):1-17. 2020.
(
pdf)
(
doi)
Polygon Simplification by Minimizing Convex Corners.
791:76-86. 2019.
(
pdf)
(
doi)
Integrated Rank-Weighted Depth.
173:51-69. 2019.
(
pdf)
(
doi)
Relating Graph Thickness to Planar Layers and
Bend Complexity.
32(4):2703-2719. 2019.
(
pdf)
(
doi)
(
arXiv:1602.07816)
Drawing Plane Triangulations with Few Segments.
77:27-39. 2019.
(
doi)
A Simple Linear-Space Data Structure for
Constant-Time Range Minimum Query.
Stephane Durocher and Robby Singh.
770:51-61. 2019.
(
pdf)
(
doi)
(
arXiv:1109.4460)
A Time-Space Trade-off for Computing the k-Visibility
Region of a Point in a Polygon.
789:13-21. 2019.
(
pdf)
(
doi)
On Combinatorial Depth Measures.
28(4):381-398. 2018.
(
pdf)
(
doi)
Competitive Online Routing on Delaunay
Triangulations.
27(4):241-253. 2017.
(
pdf)
(
doi)
Computing Conforming Partitions of Orthogonal Polygons
with Minimum Stabbing Number.
Stephane Durocher and
Saeed Mehrabi.
689:157-168. 2017.
(
pdf)
(
doi)
Guarding Monotone Art Galleries with Sliding
Cameras in Linear Time.
44:39-47. 2017.
(
pdf)
(
doi)
The Projection Median as a Weighted Average.
8(1):78-104. 2017.
(
pdf)
(
doi)
Guarding Orthogonal Art Galleries
with Sliding Cameras.
65:12-26. 2017.
(
pdf)
(
doi)
Drawing Planar Graphs with Reduced Height.
21(4):433-453. 2017.
(
pdf)
(
doi)
Thickness and Colorability of Geometric Graphs.
56:1-18. 2016.
(
pdf)
(
doi)
Linear-Space Data Structures for Range
Frequency Queries on Arrays and Trees.
74(1):344-366. 2016.
(
pdf)
(
doi)
Low Space Data Structures for Geometric Range
Mode Query.
581:97-101. 2015.
(
pdf)
(
doi)
Complexity of Barrier Coverage with
Relocatable Sensors in the Plane.
579:64-73. 2015.
(
pdf)
(
doi)
Searching on a Line: A Complete Characterization
of the Optimal Solution.
569:24-42. 2015.
(
pdf)
(
doi)
(
arXiv:1310.1048)
On Graphs That Are Not PCGs.
571:78-87. 2015.
(
pdf)
(
doi)
Plane 3-trees: Embeddability and Approximation.
29(1):405-420. 2015.
(
pdf)
(
doi)
Linear-Space Data Structures for Range Minority Query
in Arrays.
72(4):901-913. 2015.
(
pdf)
(
doi)
Bounding Interference in Wireless Ad Hoc
Networks with Nodes in Random Position.
23(4):1078-1091. 2015.
(
pdf)
(
doi)
(
arXiv:1111.6689)
The Hausdorff Core Problem on Simple Polygons.
5(1):14-40. 2014.
(
pdf)
(
doi)
Linear-Space Data Structures for Range Mode Query
in Arrays.
55(4):719-741. 2014.
(
pdf)
(
doi)
Robust Nonparametric Simplification
of Polygonal Chains.
23(6):427-441. 2013.
(
pdf)
(
doi)
(
arXiv:1205.6717)
A Note on Minimum-Segment Drawings of Planar
Graphs.
17(3):301-328. 2013.
(
pdf)
(
doi)
Bounding the Locality of
Distributed Routing Algorithms.
26(1):39-58. 2013.
(
pdf)
(
doi)
Faster Optimal Algorithms for Segment Minimization
with Small Maximal Value.
161(3):317-329. 2013.
(
pdf)
(
doi)
Range Majority in Constant Time and Linear
Space.
222:169-179. 2013.
(
pdf)
(
doi)
Cool-lex Order and k-ary Catalan Structures.
16:287-307. 2012.
(
pdf)
(
doi)
Untangled Monotonic Chains and Adaptive Range
Search.
412(32):4200-4211. 2011.
(
pdf)
(
doi)
A Note on Improving the Performance of
Approximation Algorithms for Radiation Therapy.
111(7):326-333. 2011.
(
pdf)
(
doi)
(
arXiv:0905.4930)
Modelling Gateway Placement in Wireless Networks:
Geometric k-Centres of Unit Disc Graphs.
44(5):286-302. 2011.
(
pdf)
(
doi)
Reconstructing Polygons from Scanner Data.
412(32):4161-4172. 2011.
(
pdf)
(
doi)
Comparing Geometric Models for Orientation: Medial
vs. Principal Axes.
4(6):710-712. Invited contribution, 2011.
(
pdf)
(
link)
(
doi)
A Misunderstanding of Principal and Medial Axes?
Reply to Sturz and Bodily (2011).
7(5):649-650. Invited contribution, 2011.
(
pdf)
(
doi)
An Improved Line-Separable Algorithm for Discrete
Unit Disk Cover.
2(1):77-87. 2010.
(
pdf)
(
doi)
On Routing with Guaranteed Delivery in
Three-Dimensional Ad Hoc Wireless Networks.
16(1):227-235. 2010.
(
pdf)
(
doi)
Balancing Traffic Load Using One-Turn Rectilinear
Routing.
10(1-2):93-120. 2009.
(
pdf)
(
doi)
The Projection Median of a Set of Points.
42(5):364-375. 2009.
(
pdf)
(
doi)
Kinetic Maintenance of Mobile k-Centres on
Trees.
157(7):1432-1446. 2009.
(
pdf)
(
doi)
Bounded-Velocity Approximation of Mobile Euclidean
2-Centres.
18(3):161-183. 2008.
(
pdf)
(
doi)
The Steiner Centre: Stability, Eccentricity, and
Applications to Mobile Facility Location.
16(4):345-371. 2006.
(
postscript)
(
pdf)
(
doi)
The Rectilinear Crossing Number of K10
is 62.
Cops and Robbers on 1-Planar Graphs.
Stephane Durocher,
Shahin Kamali,
Myroslav Kryven,
Fengyi Liu,
Amirhossein Mashghdoust,
Avery Miller,
Pouria Zamani Nezhad,
Ikaro Penha Costa, and
Timothy Zapp.
Minimum Ply Covering of Points with Unit Disks.
CCOSKEG Discs in Simple Polygons.
Online Square Packing with Predictions.
Approximating the Smallest k-Enclosing Geodesic Disc in a Simple Polygon.
Minimum Ply Covering of Points with Unit Squares.
A Structured Latent Space for Human Body Motion Generation.
557-566. 2022.
(
doi)
(
arXiv:2106.04387)
Curve Stabbing Depth: Data Depth for Plane Curves.
Stephane Durocher and Spencer Szabados.
121-128. 2022.
(
pdf)
(
arXiv:2311.07907)
Computing Batched Depth Queries and the Depth of a Set of Points.
Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set.
Efficient Privacy-Preserving Approaches for Trajectory Datasets.
On the Restricted 1-Steiner Tree Problem.
Non-Crossing Matching of Online Points.
Clustering Moving Entities in Euclidean Space.
Stephane Durocher
and Md. Yeakub Hassan.
Watchtower for k-Crossing Visibility.
Visibility Query without Preprocessing.
Interference Minimization in k-Connected Wireless
Networks.
Stephane Durocher and
Sahar Mehrpour.
113-119. 2017.
(
pdf)
Exploring Increasing-Chord Paths and Trees.
19-24. 2017.
(
pdf)
Time-Space Trade-off for Finding the k-Visibility
Region of a Point in a Polygon.
Relating Graph Thickness to Planar Layers and
Bend Complexity.
On the Biplanar Crossing Number of Kn.
93-100. 2016.
(
pdf)
Polygon Simplification by Minimizing Convex Corners.
Realization of Simply Connected Polygonal Linkages
and Recognition of Unit Disk Contact Trees.
Duality for Geometric Set Cover and Geometric
Hitting Set Problems on Pseudodisks.
Guarding Orthogonal Terrains.
Stephane Durocher,
Ben Li, and
Saeed Mehrabi.
Exploring Test Suite Diversification and Code
Coverage in Multi-Objective Test Case Selection.
Local Routing in Convex Subdivisions.
Guarding Monotone Art Galleries with Sliding
Cameras in Linear Time.
A 3-Approximation Algorithm for Guarding
Orthogonal Art Galleries with Sliding Cameras.
Stephane Durocher and
Saeed Mehrabi.
Competitive Online Routing on Delaunay
Triangulations.
Indexed Geometric Jumbled Pattern Matching.
A (7/2)-Approximation Algorithm for Guarding
Orthogonal Art Galleries with Sliding Cameras.
Drawing HV-Restricted Planar Graphs.
Drawing Planar Graphs with Reduced Height.
Trade-offs in Planar Polyline Drawings.
On Combinatorial Depth Measures.
206-211. 2014.
(
pdf)
Drawing Plane Triangulations with Few Segments.
40-45. 2014.
(
pdf)
Low Space Data Structures for Geometric Range
Mode Query.
212-215. 2014.
(
pdf)
On Balanced +-Contact Representations.
Top-k Color Queries on Tree Paths.
Revisiting the Problem of
Searching on a Line.
Plane 3-trees: Embeddability and Approximation.
Linear-Space Data Structures for Range
Frequency Queries on Arrays and Trees.
Guarding Orthogonal Art Galleries using
Sliding Cameras: Algorithmic and Hardness Results.
Stephane Durocher and
Saeed Mehrabi.
Thickness and Colorability of Geometric Graphs.
On k-Enclosing Objects in a Coloured Point Set.
Robust Solvers for Square Jigsaw Puzzles.
249-256. 2013.
(
pdf)
(
doi)
Complexity of Barrier Coverage with
Relocatable Sensors in the Plane.
On Graphs That Are Not PCGs.
Would You Do As a Robot Commands? An Obedience Study for Human-Robot Interaction.
Derek Cormier, Gem Newman, Masayuki Nakane,
James Young, and Stephane Durocher.
1-3. 2013.
Linear-Space Data Structures for Range Minority Query
in Arrays.
Linear-Space Data Structures for Range Mode Query
in Arrays.
Robust Nonparametric Data Approximation of Point Sets
via Data Reduction.
Bounding Interference in Wireless Ad Hoc Networks
with Nodes in Random Position.
Computing Partitions of Rectilinear Polygons
with Minimum Stabbing Number.
Stephane Durocher and
Saeed Mehrabi.
On the Hardness of Point-Set Embeddability.
Hamiltonian Paths and Cycles in Planar Graphs.
The Cover Contact Graph of Discs Touching a Line.
Stephane Durocher,
Saeed Mehrabi,
Matthew Skala,
and Mohammad Abdul Wahid.
Portrait Drawing Robot with a Geometric Graph
Approach: Furthest Neighbour Theta-Graphs.
Range Majority in Constant Time and Linear
Space.
Faster Optimal Algorithms for Segment Minimization
with Small Maximal Value.
Embedding Plane 3-Trees in R2
and R3.
Realizing Site Permutations.
A Note on Minimum-Segment Drawings of Planar
Graphs.
23:303-308. 2011.
(
pdf)
Ranking and Loopless Generation of k-ary Dyck
Words in Cool-lex Order.
Finding a Hausdorff Core of a Polygon: On Convex
Polygon Containment with Bounded Hausdorff Distance.
Bounding the Locality of
Distributed Routing Algorithms.
ACM.
28:250-259. 2009.
(
pdf)
(
doi)
Reconstructing Polygons from Scanner Data.
Untangled Monotonic Chains and Adaptive Range
Search.
Practical Discrete Unit Disk Cover Using an Exact
Line-Separable Algorithm.
Modelling Gateway Placement in Wireless Networks:
Geometric k-Centres of Unit Disc Graphs.
ACM.
5:79-86. 2008.
(
pdf)
(
doi)
On the Structure of Small Motif Finding
Instances.
Balancing Traffic Load Using One-Turn Rectilinear
Routing.
Kinetic Maintenance of Mobile k-Centres on
Trees.
Minimizing the Number of Arcs Linking a Permutation
of Points in the Plane.
18:181-184. 2006.
(
postscript)
(
pdf)
The Projection Median of a Set of Points in
R2.
17:46-50. 2005.
(
postscript)
(
pdf)
The Gaussian Centre and the Projection Centre of a
Set Points in R3.
16:140-144. 2004.
(
postscript)
(
pdf)
The Gaussian Centre of a Set of Mobile Points.
15:123-127. 2003.
(
postscript)
(
pdf)
On the Hardness of Turn-Angle-Restricted Rectilinear
Cycle Cover Problems.
14:13-16. 2002.
(
postscript)
(
pdf)
Special Issue for Selected Articles from
the 30th Canadian Conference on Computational Geometry.
Proceedings of the 30th Canadian Conference
on Computational Geometry.
Special Issue for Selected Articles from
the 22nd Canadian Conference on Computational Geometry.
Proceedings of the 22nd Canadian Conference
on Computational Geometry.
Routing in Geometric Networks.
Springer. 5 pages. 2015.
(
pdf)
(
doi)
Geometric Facility Location under Continuous
Motion.
Stephane Durocher.
Graph-Theoretic and Geometric Algorithms Associated
with Moment-Based Polygon Reconstruction.
Stephane Durocher.
2-Coloring Point Guards in a k-Guarded Polygon.
Stephane Durocher,
Myroslav Kryven,
Fengyi Liu,
Amirhossein Mashghdoust, and
Ikaro Penha Costa.
Finding the k-Visibility Region of a Point
in a Simple Polygon in the Memory-Constrained Model.
191-194. 2016.
(
pdf)
Drawing Graphs Using Body Gestures.
On Geometric Duality for 2-Admissible Geometric
Set Cover and Hitting Set Problems.
A Simple Linear-Space Data Structure for
Constant-Time Range Minimum Query.
Stephane Durocher.
Reconstructing Polygons from Scanner Data.
18:51-52. 2008.
(
pdf)
Bounded-velocity Approximations of the Mobile
Euclidean 2-Centre.
15:48-50. 2005.
(
postscript)
(
pdf)
Mobile Facility Location.
Poster presented at the
MITACS
Sixth Annual Conference.
Winner of best poster award. 2005.
(
pdf)
Restricted 2-Factor Problems Arising from
Moment-Based Polygon Reconstruction.
55-57. 1999.
(
postscript)
(
pdf)