Pat Morin
 School of Computer Science
Carleton University
1125 Colonel By Drive
Ottawa Ontario
CANADA K1S 5B6
 Tel: (613)520-2600x4353
Fax: (514)520-4334
Email: morin@cs.carleton.ca
Web: http://cg.scs.carleton.ca/~morin/
Last updated: April 2, 2026

Education

Jan. 2001–Dec. 2001 NSERC Post-doctoral fellow at McGill University
Jan. 1998–Jan. 2001 PhD (Computer Science) from Carleton University
Sep. 1996–Jan. 1998 M.C.S. degree from Carleton University
Sep. 1991–May 1996 B.C.S. degree (highest honours) from Carleton University

Academic Awards

January 2021
 Faculty of Science Research Excellence Award $5 000
January 2017
 Faculty of Science Teaching Award $1 000
January 2009
 Research Achievement Award $15 000
June 2001
 Best Paper Award — SIROCCO 2001 [109]  
Jan. 2001–Dec. 2001
 NSERC Postdoctoral Fellowship $35 000/yr
May 2001
 Carleton University Senate Medal  
May 1999–Apr. 2001
 NSERC PGS-B Scholarship $19 000/yr
May 1997–Apr. 1999
 NSERC PGS-A Scholarship $16 000/yr

Research Grants

2024–2027
 NSERC Alliance International ALT=$75,000
2024–2029
 NSERC Discovery Grant ALT=$55 000
2018–2024
 NSERC Discovery Grant ALT=$48 000
2017–2018
 eCampusOntario Open Content Funding $97 390
2013–2017
 NSERC Discovery Grant ALT=$36 000
2012–2013
 SSHRC Partnership Dev $21 000
2012–2013
 NSERC ENGAGE $25 000
2009
 Carleton University Research Award $15 000
2008–2010
 NSERC Discovery Accelerator ALT=$40 000
2008–2012
 NSERC Discovery Grant ALT=$26 000
2008
 University of Sydney Research Fellowship $15 000
2008
 National ICT Australia Collaboration Grant $7 000
2008
 Ontario Innovation Trust Matching Program $24 145
2008
 Canada Foundation for Innovation New Opportunities Fund $24 145
2007
 Ontario Government Early Researcher Award $100 000
2007
 Carleton University Carty Fellowship $50 000
2006
 Belgian FNRS Collaboration Grant €5 000
2003–2007
 NSERC Discovery Grant ALT=$21 000
2004
 Ontario Innovation Trust Matching Program $83 227
2004
 Canada Foundation for Innovation New Opportunities Fund $83 227
2002
 Carleton University Startup Grant $30 000

Relevant Work Experience

Professor
Jul. 2013– Carleton University Ottawa, Canada
  Professor of computer science
   
Associate Professor
Jul. 2006–Jun. 2013 Carleton University Ottawa, Canada
  Associate professor of computer science
   
Assistant Professor
Jan. 2002–Jun. 2006 Carleton University Ottawa, Canada
  Assistant professor of computer science
   
Postdoctoral Fellow
Jan. 2001–Dec. 2001 McGill University Montréal, Canada
  NSERC-funded postdoctoral fellow
   

Current Research Interests

Graph theory and algorithms
The study of combinatorial, structural, and algorithmic problems on graphs [39,38,36,33,27,40,41,37,42,43,45,46,48,51,56,29,30]
   
Geometric computing The study of algorithmic and combinatorial geometry problems motivated by application areas such as robust statistics [93,97,118,169,121,172], geographic information systems [119,122,151,178], molecular biology and polymer physics [94,124,125,127,147], manufacturing [108,115,83,86], facility location [104,110,121,172,47], automated cartography [116], machine learning [103], and visualization [106,105,107,146]
   
Data structures The design and analysis of efficient dictionaries [12,112,120,173,53,52] and geometric data structures [121,172]
   
Online and distributed computing
The design and analysis of communication protocols and distributed algorithms [109,111,117,123,126,122,145,50,46,43]

Professional Duties

Program Committees ISAAC 2002, CCCG 2004, Adhoc Now 2005, AAIM 2006, ISAAC 2006, Adhoc Now 2006, CCCG 2006, SoCG 2007, Adhoc Now 2007, SWAT 2008, CCCG 2008, ISAAC 2008, CCCG 2009, EuroCG 2009, CATS 2009, CCCG 2010, CCCG 2012, COCOON 2012, ISAAC 2013, CCCG 2014, CCCG 2015, SoCG 2017, CCCG 2020, STACS 2021, WADS 2021, CCCG 2022, WADS 2023, SoCG 2023, CCCG 2024, ESA 2024 (Track S), WADS 2025, GD 2025
Organizing Committee CCCG 2007, Workshop on Geometry and Graphs (2013, 2014, 2015, 2016, 2017, 2018), CCCG 2017
Steering Committee Chair WADS (2023–2028)
Program Chair CCCG 2008, WADS 2023 (co-chair), WADS 2025 (co-chair)

Review Boards

 MITACS College of Reviewers (2008), Ontario Graduate Scholarship Selection Committee (2008), MRI Early Researcher Awards Adjudication Committee (2010, 2011, 2013, 2014, 2017, 2018, 2021), NSERC DG Evaluation Group 1507 (2021–2023), NSERC Discovery Horizons Fit Advisor 2023
Managing Editor Journal of Computational Geometry (2009–2024, also co-founder, with Joachim Gudmundsson)

Teaching and Supervision Duties

Students and Postdocs David R. Wood (Postdoc 2002–2004), Greg Aloupis (FCAR Postdoc 2005–2006), Meng He (Postdoc 2007–2008), Mohammad Farshi (Postdoc 2007–2008), Vida Dujmović (Postdoc 2008), Paz Carmi (Postdoc 2006–2008), Vida Dujmović (NSERC Postdoc 2004–2005, 2008–2009), Yihui Tang (Ph.D, 2008), Stefanie Wuhrer (M.C.S., 2006), Harish Gopala (M.C.S., 2004), John Howat (MCS, 2009), John Howat (PhD, 2012), Dan Chen (PhD, 2013), Zhamila Abdranova (MCS, 2013), Daniel Minor (MCS, 2015), Andre van Renssen (PhD, 2014), Sander Verdonschot (PhD, 2015), Tommy Reddad (MCS, 2015), Lucas Rioux-Maldague (MCS 2015), Luis Barba (PhD, 2016), Cory Fraser (MCS, 2016), Alexis Beingessner (MCS, 2016), Luis Fernando Schulz Xavier de Silveira (PhD 2020), Céline Yelle (MCS 2020), Hugo Akitaya (Postdoc, 2019–2020), Saeed Mehrabi (Postdoc, 2018–2020), Mehrnoosh Javarsineh (PhD, 2019–), Saman Bazarghani (PhD, 2019–), Saeed Odak (PhD, 2020–), Hussein Houdrouge (PhD, 2021–), David Worley (PhD, 2021–), Kaya Gouin (MCS 2023–), Bobby Miraftab (Postdoc, 2022–)

   
Honours Projects Michael Hodge (Diameter Finding Algorithms, W2002), Jake Denley (Generation of Random Scenery, W2004), Darcy Dunne (A Fast Algorithm for Finding the Minimum Circular Half-Covering of a 2D Point Set), Tair Bilyalov (Random 3D Terrain in Computer Games, W2005), Jeremy Gribben (Procedural Generation of Random 3D Vehicles, W2005), Christopher Johnson (Randomized Scenery in 3D Gaming, W2005), Dmitry Karasik (IOUs in BitTorrent, W2005), Vladimir Bradateanu (Dynamically Generated Random Terrain and Trees, S2005), Jamie Suomela (Random Generation of Billboard Advertising for Use in Racing Games, S2005), Gi Wu (BitTorrent IOU Extensions, S2005), Mykola Konyk (Polyhedral Surface Reconstruction, W2006), Richard Poulin (Dynamic Workflow — Graph Drawing, S2007), Irwin Zaid (Graph Hierarchies which Approximate the Complete Euclidean Graph, F2007), Shayan Negari (Application Sharing Over the Public Internet, F2007), Rajinder Wasson (A Mediawiki Sports League Extension, W2008), Daniel Minor (Cuckoo Hashing in Python, W2008), Yini He (Fast Searching in the HTML DOM, W2008), Paul Cumming (MediaWiki 2.0, W2008), Vlad Rubinov (Fast HDR, F2009), Bryan Waite (Open Source decompression algorithms, W2010), Edward Duong (Real-time HDR, W2010), Calvin Wiebe (Halia: A JavaScript DOM Querying Algorithm, F2010), Nima Hoda (Visibility-Monotonic Polygon Deflation, W2013), Troy Hildebrandt (Robust Constructive Solid Geometry, W2013), Christian Delahouse (Data Structures for Approximate String Searching, W2015) Joel Scarfone (A C++ Eytzinger Library, F2017), Basim Ramadhan (The Lovelace Engine: A Simple & Secure Submission Server, W2018), Omar Ben Ismail (Interactive Visualization of Data Structures, W2018), William Dullemond (Using Bloom Filters to Test Set Differences over a Network, F2018), Noah Steinberg (Performance of Hash Table Implementations, W2019), Nathaniel Arnill (An Implementation of Product Structure, W2021), Kaya Gouin (Tripod Decompositions of Planar Graphs, W2023)
   

Summer Undergraduates

Christian Leger (Relations Between Binary and Ternary Trees, S2005), Christian Muise (Data Structures for the HTML DOM, S2007), Irwin Zaid (Hierarchical Spanners, S2007), John Howat (Property-Rich Succinct Data Structures, S2007), James Mendek (Distribution-Sensitive Point Location, S2008), Shane Smith (Simple Compiler Compiler, S2010), Nima Hoda (Basic Data Structures, S2011), Nima Hoda (Polygon Reconfiguration, S2012), Troy Hildebrand (3DCSS in Chromium, S2013), Jennifer Hood (Graph Drawing, S2015), Gahen Thanabalasingam (Data Structures, S2017), Sean Hodges (Data Structures, S2017), Martin Lunn (Data Structures, S2017), Ivana Marusic (Graph Algorithms, S2020), Eden Zebene (Connected Dominating Sets, S2024), Simon Tran (Connected Dominating Sets, S2024)
   

Committees Lab Committee (2002, 2003, 2004)
  Hiring Commitee (2003, 2004, 2005, 2006, 2007, 2014, 2020, 2021, 2023)
  Curriculum Committee (2003)
  Departmental Promotions and Tenure Committee (2003, 2007, 2014, 2020, 2021, 2023)
  Faculty Promotions and Tenure Committee (2020)
  RAA Evaluation Committee (2013, 2014, 2016)
  Development Grant Review Committee (2017)
  Tenure and Promotion Appeals Committee (2019, 2020)
  Field Institute Activities Committee (2019–2021, 2023)
  SCS Executive Committe (2021)
  SCS Tenure and Promotion Committee Chair (2020, 2021, 2023)
  Faculty of Science Tenure and Promotion Committee (2020, 2021, 2023)
   
Courses Taught COMP5408 Advanced Data Structures (W2002, F2003, F2004, W2006, W2007, W2008, F2009, W2011, W2012, W2013, W2014, F2021)
  COMP4804 Algorithms II (W2003, W2004, W2005, W2006, W2010, W2017)
  COMP4900/5900 Computational Molecular Biology (W2006, W2007)
  COMP3804 Algorithms I (W2006)
  COMP3002 Compiler Construction (W2003, W2004, W2005, W2008, F2009, W2011, F2011)
  COMP2804 Discrete Structures II (F2019ALT=2, W2020, F2020, W2022)
  COMP2405 Internet Application Programming (W2007, W2008)
  COMP2402 Data Structures (F2010, F2011, F2012, F2013, F2014, F2016, F2018, F2020)
  COMP5804 OCICS Graduate Seminar (2004, 2005, 2006, 2007, 2008)
  COMP1405 Introduction to Programming (F2012, F2013, F2014)

Publications

References

1
Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin.
Adjacency labelling of proper minor-closed graph classes.
Submitted to FOCS 2026 in April 2026.

2
Hussein Houdrouge, Babak Miraftab, and Pat Morin.
2-dimensional unit vector flows.
Submitted to Electronic Journal of Combinatorics in March 2026.

3
Babak Miraftab, Pat Morin, and Yelena Yuditsky.
Basis number and pathwidth.

4
Quentin Claus, Jędrzej Hodor, Gwenaël Joret, and Pat Morin.
Excluding an apex-forest or a fan as quickly as possible.
Submitted to SIAM Journal on Discrete Mathematics in January 2026.

5
Vida Dujmović, Pat Morin, Sergey Norin, and David R. Wood.
ALT=-colouring planar graphs.
Submitted to Combinatorics, Probability & Computing in July 2025.

6
Vida Dujmović, Gwenaël Joret, Piotr Micek, and Pat Morin.
Erdős-Pósa property of cycles that are far apart.
Submitted to Journal of the London Mathematical Society in July 2025 and revised in February 2026
Submitted to Proceedings of the London Mathematical Society in January 2025 and rejected in July 2025.

7
Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, Pat Morin, and Saeed Odak.
Connected dominating sets in triangulations.
Submitted to SoCG 2024 in December 2023 and rejected in February 2024.
Submitted to SODA 2025 in July 2024 and rejected in October 2024.

References

8
Pat Morin.
Open Data Structures (in Pseudocode).
Web, 2014.
A freely-available open content textbook.

9
Pat Morin.
Open Data Structures: An Introduction.
Athabasca University Press, Edmonton, 2013.
Also freely available as Open Data Structures (in Java) at opendatastructures.org.

10
Pat Morin.
Open Data Structures (in C++).
Web, 2012.
A freely-available open content textbook.

References

11
Vida Dujmović and Pat Morin.
Free sets in planar graphs: History and applications.
In János Pach and Géza Tóth, editors, Courses in Discrete and Computational Geometry, Bolyai Society Mathematical Studies. Springer-Verlag, 2026.

12
Pat Morin.
Hash tables.
In Dinesh Mehta and Sartaj K. Sahni, editors, Handbook of Data Structures and Applications, chapter 9. CRC Press, 2004.

References

13
Hussein Houdrouge, Babak Miraftab, and Pat Morin.
Separation number and treewidth, revisited.
Discrete Mathematics.
Accepted, pending minor revisions, in March 2026.

14
Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood.
Planar graphs in blowups of fans.
Advances in Combinatorics.
Accepted in January 2026.
Prelliminary version appeared at SODA2025.

15
Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh, and Pat Morin.
Asymptotically optimal vertex ranking of planar graphs.
Journal of Combinatorial Theory, Series B.
Accepted, pending revisions, in January 2026.

131
Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor, Gwenaël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, and David R. Wood.
The grid-minor theorem revisited.
Combinatorica, 45(62), 2025.
Accepted in June 2025. Preliminary version appeared at SoDA 2024.

17
John Iacono, Piotr Micek, Pat Morin, and Bruce Reed.
Vertex ranking of degenerate graphs.
Electronic Journal of Combinatorics.
Accepted, pending minor revisions, in December 2024.

18
Vida Dujmović, Gwenaël Joret, Piotr Micek, and Pat Morin.
Tight bound for the Erdős-Pósa property of tree minors.
Combinatorics, Probability and Computing, 34(2):321–325.

19
Vida Dujmović, Pat Morin, David R. Wood, and David Worley.
Grid minors and products.
Electronic Journal of Combinatorics.
Accepted, pending minor revisions, in October 2024.

20
Marc Distel, Vida Dujmović, David Eppstein, Robert Hickingbotham, Gwenaël Joret, Pat Morin, Michał Seweryn, and David R. Wood.
Product structure extension of the Alon–Seymour–Thomas theorem.
SIAM Journal on Discrete Mathematics.
Accepted, pending minor revisions, in March 2024.

21
Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, Mehrnoosh Javarsineh, and Pat Morin.
Linear versus centred chromatic numbers.
Journal of Graph Theory.
Accepted, pending minor revisions, in March 2024.

22
Carla Binucci, Giuseppe Di Battista, Walter Didimo, Vida Dujmovic, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, and Alessandra Tappini.
Graphs drawn with some vertices per face: Density and relationships.
IEEE Access, 12:68828–68846, 2024.

23
Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood.
Bounded-degree planar graphs do not have bounded-degree product structure.
Electronic Journal of Combinatorics, 31.2:P2.51, 2024.

24
Paz Carmi, Matthew J. Katz, and Pat Morin.
Stabbing pairwise intersecting disks by four points.
Discrete & Computational Geometry, 70:1751–1784, 2023.

25
Vida Dujmović, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood.
The excluded tree minor theorem revisited.
Combinatorics, Probability and Computing, 33(1):85–90, 2024.

26
Louis Esperet, Gwenaël Joret, and Pat Morin.
Sparse universal graphs for planarity.
Journal of the London Mathematical Society, 108(4):1333–1357, 2023.

27
Vida Dujmović, Pat Morin, and David R. Wood.
Graph product structure for non-minor-closed classes.
Journal of Combinatorial Theory, Series B, 162:34–67, 2023.

28
Prosenjit Bose, Paz Carmi, Vida Dujmović, Saeed Mehrabi, Fabrizio Montecchiani, Pat Morin, and Luís Fernando Shulz Xavier da Silveira.
Geodesic obstacle representation of graphs.
Computational Geometry: Theory and Applications, 109, 2023.
Preliminary version appeared at ICALP 2018.

29
Vida Dujmović and Pat Morin.
Dual circumference and collinear sets.
Discrete & Computational Geometry, 69:26–50, 2023.

30
Oswin Aichhozer, Manuel Borazzo, Prosenjit Bose, Jean Cardinal, Fabrizio Frati, Pat Morin, and Birgit Vogtenhuber.
Drawing graphs as spanners.
Discrete & Computational Geometry, 68:774–795, 2022.
Preliminary version appeared at WG 2021.

31
Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh, Pat Morin, and David R. Wood.
Separating layered treewidth and row treewidth.
Discrete Mathematics & Theoretical Computer Science, 24(1), 2022.

32
Saman Bazarghani, Paz Carmi, Vida Dujmović, and Pat Morin.
ALT= grids have unbounded anagram-free chromatic number.
Electronic Journal of Combinatorics, 29(3), 2022.

33
Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood.
Clustered 3-colouring graphs of bounded degree.
Combinatorics, Probability and Computing, 31:123–135, 2022.

34
Vida Dujmović, David Eppstein, Robert Hickingbotham, Pat Morin, and David R. Wood.
Stack-number is not bounded by queue-number.
Combinatorica, 42:151–164, 2022.

35
A. K. Abu-Affash, P. Carmi, A. Maheshwari, P. Morin, M. Smid, and S. Smorodinsky.
Approximating maximum diameter-bounded subgraph in unit disk graphs.
Discrete & Computational Geometry, 66:1401–1414, 2021.
Preliminary version appears at SoCG 2018.

36
Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin.
Adjacency labelling for planar graphs (and beyond).
Journal of the ACM, 68(6):42:1–33, 2021.
Preliminary version appeared at FOCS 2020.

37
Vida Dujmović, Fabrizio Frati, Daniel Gonçalves, Pat Morin, and Günter Rote.
Every collinear set in a planar graph is free.
Discrete & Computational Geometry, 65:999–1027, 2021.
Preliminary version appeared at SODA 2019.

38
Pat Morin.
A fast algorithm for the product structure of planar graphs.
Algorithmica, 83(5):1544–1558, 2021.

39
Vida Dujmović, Pat Morin, and Céline Yelle.
Two results on layered pathwidth and linear layouts.
Journal of Graph Algorithms and Applications, 25(1):43–57, 2021.

40
Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood.
Planar graphs have bounded queue-number.
Journal of the ACM, 67(4):22:1–22:38, 2020.
Preliminary version appeared at FOCS 2019.

41
Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, and David R. Wood.
Minor-closed graph classes with bounded layered pathwidth.
SIAM Journal on Discrete Mathematics, 34(3):1693–1709, 2020.
Accepted, pending minor revisions, in September 2019.

42
Boris Aronov, Vida Dujmović, Pat Morin, Aurélien Ooms, and Luís Fernando Shulz Xavier da Silveira.
More Turán-type theorems for triangles in convex point sets.
Electronic Journal of Combinatorics, 26(1), 2019.
P1.8 (26 pages).

43
Luc Devroye, Vida Dujmović, Alan Frieze, Abbas Mehrabian, Pat Morin, and Bruce Reed.
Notes on growing a tree in a graph.
Random Structures & Algorithms, 55:290–312, 2019.

44
Vida Dujmović, Gwenaël Joret, Pat Morin, Sergey Norin, and David R. Wood.
Corrigendum to “Orthogonal tree decompositions of graphs”.
SIAM Journal on Discrete Mathematics, 32(4):3003–3004, 2018.

45
Vida Dujmović, Gwenaël Joret, Pat Morin, Sergey Norin, and David R. Wood.
Orthogonal tree decompositions of graphs.
SIAM Journal on Discrete Mathematics, 32(2):839–863, 2018.

46
Luc Devroye and Pat Morin.
A note on interference in random networks.
Computational Geometry: Theory and Applications, 67:2–10, 2018.
Preliminary version appeared at CCCG 2012.

47
Ahmad Biniaz, Prosenjit Bose, David Eppstein, Anil Maheshwari, Pat Morin, and Michiel Smid.
Spanning trees in multipartite geometric graphs.
Algorithmica, 80(11):3177–3191, November 2018.

48
Vida Dujmović, Pat Morin, and David R. Wood.
Layered separators in minor-closed graph classes with applications.
Journal of Combinatorial Theory, Series B, 127:111–147, 2017.
Preliminary version appeared at FOCS 2013.

49
Pat Morin, Wolfgang Mulzer, and Tommy Reddad.
Encoding arguments.
ACM Computing Surveys, 50(3):46:1–36, 2017.

50
Pat Morin and Sander Verdonschot.
On the average number of edges in theta graphs.
Online Journal of Analytic Combinatorics.
Accepted in July 2016.
Preliminary version appeared at ANALCO 2014.

51
Prosenjit Bose, Vida Dujmović, Pat Morin, and Lucas Rioux-Maldague.
New bounds for facial nonrepetitive colouring.
Graphs and Combinatorics, 33(4):817–832, 2017.

52
Paul-Virak Khuong and Pat Morin.
Array layouts for comparison-based searching.
ACM Journal of Experimental Algorithmics, 22(1), 2017.
Article No. 1.3 (39 pages).

53
Prosenjit Bose, Rolf Fagerberg, John Howat, and Pat Morin.
Biased predecessor search.
Algorithmica, 76(4):1097–1105, 2016.
Preliminary version appeared at LATIN 2014.

54
Prosenjit Bose, Jean-Lou De Carufel, Pat Morin, André van Renssen, and Sander Verdonschot.
Towards tight bounds on theta-graphs: More is not always better.
Theoretical Computer Science, 616:70–93, 2016.

55
Prosenjit Bose, Pat Morin, and André van Renssen.
The price of order.
International Journal of Computational Geometry and Applications, 26(3):135–149, 2016.
Preliminary version appeared at ISAAC 2014.

56
Greg Aloupis, Luis Barba, Paz Carmi, Vida Dujmović, Fabrizio Frati, and Pat Morin.
Compatible connectivity augmentation of planar disconnected graphs.
Discrete & Computational Geometry, 54(2):459–480, 2015.
Preliminary version appeared at SODA 2015.

57
Prosenjit Bose, Vida Dujmović, Nima Hoda, and Pat Morin.
Visibility-monotonic polygon deflation.
Contributions to Discrete Mathematics, 10(1):1–21, 2015.
Preliminary version appears in Proceedings of CCCG 2012.

58
Vida Dujmović and Pat Morin.
On obstacle numbers.
Electronic Journal of Combinatorics, 22(3), 2015.
P3.1 (7 pages).

59
Vida Dujmović, Pat Morin, and Michiel Smid.
Average stretch factor: How low does it go?
Discrete & Computational Geometry, 53(2):296–326, 2015.

60
Prosenjit Bose, Pat Morin, André van Renssen, and Sander Verdonschot.
The ALT= graph is a spanner.
Computational Geometry: Theory and Applications, 48(2):108–119, 2015.
Preliminary version appears in Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013).

61
Vida Dujmović, Pat Morin, and Adam Sheffer.
Crossings in grid drawings.
Electronic Journal of Combinatorics, 21(1), 2014.
P1.41 (18 pages).

62
Prosenjit Bose, Vida Dujmović, Pat Morin, and Michiel Smid.
Robust geometric spanners.
SIAM Journal on Computing, 42(4):1720–1736, 2013.
Preliminary version appears in Proceedings of the Twenty-Ninth ACM Symposium on Computational Geometry (SoCG 2013), ACM Press, 2013.

63
Dan Chen and Pat Morin.
Approximating majority depth.
Computational Geometry: Theory and Applications, 46(9):1059–1064, 2013.
Special issue of selected papers from CCCG 2012.

64
Dan Chen, Pat Morin, and Uli Wagner.
Absolute approximation of Tukey depth: Theory and experiments.
Computational Geometry: Theory and Applications, 46(5):566–573, 2013.
Special issue on Geometric Optimization.

65
B. Ballinger, Nadia Benbernou, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Vida Dujmović, Robin Flatland, Ferran Hurtado, John Iacono, Anna Lubiw, Pat Morin, Vera Sacristán, Diane Souvaine, and Ryuhei Uehara.
Coverage with ALT=-transmitters in the presence of obstacles.
Journal of Combinatorial Optimization, 25(2):208–233, March 2013.
Preliminary version appears in Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA2010), Part II: 1-15, 2010.

66
Dan Chen, Olivier Devillers, John Iacono, Stefan Langerman, and Pat Morin.
Oja centers and centers of gravity.
Computational Geometry: Theory and Applications, 46(2):140–147, 2013.
Special issue of selected papers from CCCG 2010.

67
Prosenjit Bose, Karim Douïeb, Vida Dujmović, John Howat, and Pat Morin.
Fast local searches and updates in bounded universes.
Computational Geometry: Theory and Applications, 46(2):181–189, 2013.
Special issue of selected papers from CCCG 2010.

68
David Charlton, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Pat Morin, and Ryuhei Uehara.
Ghost chimneys.
International Journal of Computational Geometry and Applications, 22(3):207–214, 2012.
Preliminary version appears in Proceedings of CCCG 2010.

69
Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman, and Pat Morin.
Entropy, triangulation, and point location in planar subdivisions.
ACM Transactions on Algorithms, 8(3):29:1–29:18, 2012.

70
Prosenjit Bose, Karim Douïeb, and Pat Morin.
Skip lifts: A probabilistic alternative to red-black trees.
Journal of Discrete Algorithms, 14:13–20, 2012.
Special issue of selected papers from the International Workshop on Combinatorial Algorithms (IWOCA 2010).

71
Prosenjit Bose, John Howat, and Pat Morin.
A distribution-sensitive dictionary with low space overhead.
Journal of Discrete Algorithms, 10:140–145, 2012.
Preliminary version appears in Proceedings of the 16th International Workshop on Algorithms and Data Structures (WADS 2009), LNCS, pages 110-118. Springer, 2009.

72
Prosenjit Bose, Eric Chen, Meng He, Anil Maheshwari, and Pat Morin.
Succinct geometric indexes supporting point location.
ACM Transactions on Algorithms, 8(2):10:1–10:26, April 2012.
Preliminary version appeared in Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pages 635-644, 2009.

73
Dan Chen, Vida Dujmović, Luc Devroye, and Pat Morin.
Memoryless routing in convex subdivisions: Random walks are optimal.
Computational Geometry: Theory and Applications, 45(4):178–185, 2012.
Preliminary version appears at EuroCG 2010.

74
Vida Dujmović, John Howat, and Pat Morin.
Biased range trees.
Algorithmica, 62(1):21–37, 2012.
Preliminary version appeared in Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pages 486–495, 2009.

75
Vida Dujmović, Joachim Gudmundsson, Pat Morin, and Thomas Wolle.
Notes on large angle crossing graphs.
Chicago Journal of Theoretical Computer Science, 2011.
Special issue of selected papers from Computing: The Australasian Theory Symposium (CATS 2010).

76
Kevin Buchin, Maarten Löffler, Wolfgang Mulzer, and Pat Morin.
Delaunay triangulation of imprecise points simplified and extended.
Algorithmica, 61(3):674–693, 2011.
Preliminary version appears in Proceedings of the 16th International Workshop on Algorithms and Data Structures (WADS 2009), LNCS. Springer, 2009.

77
Evangelos Kranakis, Danny Krizanc, and Pat Morin.
Randomized rendez-vous with limited memory.
ACM Transactions on Algorithms, 7(3):34:1–34:12, July 2011.
Preliminary version appears in Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN2008), pages 605-616, 2008.

78
Prosenjit Bose, Paz Carmi, Ferran Hurtado, and Pat Morin.
A generalized Winternitz theorem.
Journal of Geometry, 100:29–35, 2011.

79
Joachim Gudmundsson, Pat Morin, and Michiel Smid.
Algorithms for marketing-mix optimization.
Algorithmica, 60(4), 2011.

80
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, and Michiel Smid.
Sigma-local graphs.
Journal of Discrete Algorithms, 8:15–23, 2010.

81
Luc Devroye, Joachim Gudmundsson, and Pat Morin.
On the expected maximum degree of Gabriel and Yao graphs.
Advances in Applied Probability, 41(4):1123–1140, 2009.

82
Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Stefan Langerman, Pat Morin, and David R. Wood.
A polynomial bound for untangling geometric planar graphs.
Discrete & Computational Geometry, 42(2):570–585, 2009.
Preliminary version appeared at Topological and Geometric Graph Theory (TGGT 2008).

83
Prosenjit Bose, Pat Morin, Michiel Smid, and Stefanie Wuhrer.
Clamshell casting.
Algorithmica, 55(4):666–702, 2009.
Preliminary version appears in Proceedings of CAD'07.

84
Prosenjit Bose, Vida Dujmović, Ferran Hurtado, and Pat Morin.
Connectivity-preserving transformations of binary images.
Computer Vision and Image Understanding, 113(10):1027–1104, October 2009.

85
Rossen Atanassov, Prosenjit Bose, Matthieu Couture, Anil Maheshwari, Pat Morin, Michel Paquette, Michiel Smid, and Stefanie Wuhrer.
Algorithms for optimal outlier removal.
Journal of Discrete Algorithms, 7:239–248, 2009.

86
Prosenjit Bose, Pat Morin, Michiel Smid, and Stefanie Wuhrer.
Rotationally monotone polygons.
Computational Geometry: Theory and Applications, 42:471–483, 2009.
See also [171].

87
Jeff Erickson, Ferran Hurtado, and Pat Morin.
Centerpoint theorems for wedges.
Discrete Mathematics & Theoretical Computer Science, 11(1):45–54, 2009.

88
Prosenjit Bose, Paz Carmi, Matthieu Couture, Anil Maheshwari, Pat Morin, and Michiel Smid.
Spanners of complete ALT=-partite geometric graphs.
SIAM Journal on Computing, 38(5):1803–1820, 2009.
Preliminary version appears in Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN2008), 2008.

89
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin, David R. Wood, and Stefanie Wuhrer.
A characterization of the degree sequences of 2-trees.
Journal of Graph Theory, 58(3):191–209, 2008.
Preliminary version appears in Proceedings of ANALCO 2007.

90
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, and Yihui Tang.
On the false-positive rate of Bloom filters.
Information Processing Letters, 108:210–213, 2008.

91
Paz Carmi, Vida Dujmović, Pat Morin, and David R. Wood.
Distinct distances in graph drawings.
Electronic Journal of Combinatorics, 15(R107), August 2008.

92
David Bremner, Dan Chen, John Iacono, Stefan Langerman, and Pat Morin.
Output-sensitive algorithms for Tukey depth and related problems.
Statistics and Computing, 18(3):259–266, September 2008.

93
Pat Morin.
An optimal randomized algorithm for ALT=-variate zonoid depth.
Computational Geometry: Theory and Applications, 39(3):229–235, 2008.

94
Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir, and Michael Soss.
Computing the detour and spanning ratio of paths, trees and cycles in 2d and 3d.
Discrete & Computational Geometry, 39(1):17–37, 2008.
Related results are contained in Conference Paper [147].

95
Erik D. Demaine, Jeff Erickson, Danny Krizanc, Henk Meijer, Pat Morin, Mark Overmars, and Sue Whitesides.
Realizing partitions respecting full and partial order information.
Journal of Discrete Algorithms, 6:51–58, 2008.
Preliminary version appears in Proceedings of the Australasian Workshop on Combinatorial Algorithms (AWOCA 2005), pages 105-114, 2005.

96
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, and Godfried T. Toussaint.
Unfolding polyhedral bands.
Computational Geometry: Theory and Applications, 39(1):30–42, 2008.
Special issue of selected papers from The 16th Canadian Conference on Computational Geometry (CCCG 2004), 2004.

97
Harish Gopala and Pat Morin.
Algorithms for bivariate zonoid depth.
Computational Geometry: Theory and Applications, 39(1):2–13, 2008.
Special issue of selected papers from the 16th Canadian Conference on Computational Geometry (CCCG 2004).

98
Greg Aloupis, Prosenjit Bose, and Pat Morin.
Reconfiguring triangulations with edge flips and point moves.
Algorithmica, 47(4):367–378, 2007.
Special issue of selected papers from the 12th International Symposium on Graph Drawing, pages 1–11, volume 3383 of LNCS, Springer-Verlag.

99
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, Stefan Langerman, John Iacono, and Pat Morin.
Geodesic ham-sandwich cuts.
Discrete & Computational Geometry, 37(3):325–330, 2007.
Preliminary version appears in Proceedings of the Twentieth ACM Symposium on Computational Geometry (SoCG 2004), pages 1-9. ACM Press, 2004.

100
Prosenjit Bose, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, and Jan Vahrenhold.
Space-efficient geometric divide-and-conquer algorithms.
Computational Geometry: Theory and Applications, 37(3):209–227, 2007.
Preliminary version appears in Proceedings of the 20th European Workshop on Computational Geometry (EWCG 2004).

101
Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, and David R. Wood.
Simultaneous diagonal flips in plane triangulations.
Journal of Graph Theory, 54(4):307–330, 2006.
Preliminary version appears in Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pages 212-221, 2006.

102
Danny Krizanc, Pat Morin, and Michiel Smid.
Range mode and range median queries on lists and trees.
Nordic Journal of Computing, 12:1–17, 2005.
Preliminary version appears in Proceedings of the Fourteenth Annual International Symposium on Algorithms and Computation (ISAAC 2003), volume 1906 of LNCS, pages 517-526, 2003.

103
David Bremner, Erik D. Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, and Godfried T. Toussaint.
Output-sensitive algorithms for computing nearest-neighbour decision boundaries.
Discrete & Computational Geometry, 33(4):593–604, 2005.
Preliminary version appears in Proceedings of the Workshop on Algorithms and Data Structures (WADS 2003), pages 451–461, LNCS, 2748, Springer-Verlag, 2003.

104
Stefan Langerman and Pat Morin.
Covering things with things.
Discrete & Computational Geometry, 33(4):717–729, 2005.
Preliminary version appears in Proceedings of the 10th European Symposium on Algorithms (ESA 2002), pages 662–673, LNCS 2461, Springer-Verlag, 2002.

105
Vida Dujmović, Pat Morin, and David R. Wood.
Layout of graphs with bounded tree-width.
SIAM Journal on Computing, 34(3):553–579, 2005.

106
Pat Morin and David R. Wood.
Three-dimensional 1-bend graph drawings.
Journal of Graph Algorithms and Applications, 8(3):357–366, 2004.
Preliminary version appears in Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG 2004).

107
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, and David R. Wood.
The maximum number of edges in a three-dimensional grid-drawing.
Journal of Graph Algorithms and Applications, 8(1):21–26, 2004.
Preliminary version appeared at The 19th European Workshop on Computational Geometry (EuroCG 2003).

108
Pat Morin and Jason Morrison.
The geometry of carpentry and joinery.
Discrete Applied Mathematics, 144(3):374–380, 2004.
Special issue of selected papers from Fun with Algorithms 2 (FUN 2001).

109
Prosenjit Bose and Pat Morin.
Competitive online routing in geometric graphs.
Theoretical Computer Science, 324(2–3):273–288, 2004.
Special Issue: In Memoriam, Steve Seiden. Preliminary version appears in Proceedings of the VIIIth International Colloquium on Structural Information and Communication Complexity (SIROCCO 2001), pages 35–44, 2001.

110
Prosenjit Bose, Pat Morin, and Antoine Vigneron.
Packing two disks into a polygonal environment.
Journal of Discrete Algorithms, 2(3):373–380, 2004.
Preliminary version appears in Proceedings of The 7th Annual International Computing and Combinatorics Conference (COCOON 2001), pages 142–149, LNCS 2108, Springer-Verlag, 2001.

111
Prosenjit Bose and Pat Morin.
Online routing in triangulations.
SIAM Journal on Computing, 33(4):937–951, 2004.
Preliminary version appears in Proceedings of the Tenth International Symposium on Algorithms and Computation (ISAAC'99), pages 113–122, LNCS 1741, Springer-Verlag, 1999.

112
Luc Devroye, Pat Morin, and Alfredo Viola.
On worst case Robin-Hood hashing.
SIAM Journal on Computing, 33(4):923–936, 2004.

113
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, and Godfried T. Toussaint.
Space-efficient planar convex hull algorithms.
Theoretical Computer Science, 321(1):25–40, 2004.
Special issue of selected papers from Latin American Theoretical INformatics (LATIN 2002).

114
Prosenjit Bose, Joachim Gudmundsson, and Pat Morin.
Ordered theta graphs.
Computational Geometry: Theory and Applications, 28(1):11–18, 2004.
Special issue of selected papers from The 14th Canadian Conference on Computational Geometry (CCCG 2002).

115
Prosenjit Bose and Pat Morin.
Testing the quality of manufactured disks and balls.
Algorithmica, 38(2):161–177, 2004.
Special issue on Shape Algorithmics (Remco C. Veltkamp, editor).

116
Mark de Berg, Prosenjit Bose, Otfried Cheong, and Pat Morin.
On simplifying dot maps.
Computational Geometry: Theory and Applications, 27(1):43–62, 2004.
Special issue of selected papers from the Xth European Conference on Computational Geometry (EuroCG 2002).

117
Prosenjit Bose, Danny Krizanc, Stefan Langerman, and Pat Morin.
Asymmetric communication protocols via hotlink assignments.
Theory of Computing Systems, 36(6):655–661, 2003.
Special issue of selected papers from the IXth International Colloquium on Structural Information and Communication Complexity (SIROCCO 2002).

118
Peter Braß, Laura Heinrich-Litan, and Pat Morin.
Computing the center of area of a convex polygon.
International Journal of Computational Geometry and Applications, 13:439–445, 2003.

119
Prosenjit Bose, Marc van Kreveld, Anil Maheshwari, Pat Morin, and Jason Morrison.
Translating a regular grid over a point set.
Computational Geometry: Theory and Applications, 25(1–2):21–34, 2003.
Special issue of selected papers from the The 17th European Workshop on Computational Geometry (EuroCG 2001), 2001. Preliminary version appears in Proceedings of the 7th Annual Workshop on Algorithms and Data Structures (WADS 2001), pages 180–191, LNCS 2125, Springer-Verlag, 2001.

120
Luc Devroye and Pat Morin.
Cuckoo hashing: Further analysis.
Information Processing Letters, 86(4):215–219, 2003.

121
Prosenjit Bose, Anil Maheshwari, and Pat Morin.
Fast approximations for sums of distances, clustering and the Fermat-Weber problem.
Computational Geometry: Theory and Applications, 24(3):135–146, 2002.
Preliminary version appears in IX Encuentros de Geometría Computacional (9EGC), 2001.

122
Prosenjit Bose and Pat Morin.
An improved algorithm for subdivision traversal without extra storage.
International Journal of Computational Geometry and Applications, 12(4):297–308, 2002.
Special issue of selected papers from the 11th Annual International Symposium on Algorithms and Computation (ISAAC 2000).

123
Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Alejandro López-Ortiz, Pat Morin, and J. Ian Munro.
Online routing in convex subdivisions.
International Journal of Computational Geometry and Applications, 12(4):283–296, 2002.
Special issue of selected papers from the 11th Annual International Symposium on Algorithms and Computation (ISAAC 2000).

124
J. A. Calvo, Danny Krizanc, Pat Morin, Michael Soss, and Godfried T. Toussaint.
Convexifying polygons with simple projections.
Information Processing Letters, 80(2):81–86, 2001.

125
Thomas Fevens, A. Mesa A. Hernandez, Pat Morin, Michael Soss, and Godfried T. Toussaint.
Simple polygons with an infinite sequence of deflations.
Beiträge zur Algebra und Geometrie (Contributions to Algebra and Geometry), 42(2):307–311, 2001.

126
Prosenjit Bose, Pat Morin, Ivan Stojmenović, and Jorge Urrutia.
Routing with guaranteed delivery in ad hoc wireless networks.
Wireless Networks, 7(6):609–616, 2001.
Special issue of selected papers from the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM'99).

127
Hee-Kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicholas Hanusse, Evangelos Kranakis, and Pat Morin.
Flipping your lid.
Geombinatorics, X(2):57–63, 2000.
Preliminary version appears in Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG'00).

References

128
Prosenjit Bose, Pat Morin, and Karthik Murali.
Cops and robbers for graphs on surfaces with crossings.
In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS2025).
Submitted to European Journal of Combinatorics in February 2026.

129
Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond.
Local certification of geometric graph classes.
In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS2024), 2024.
Submitted to Computing in Geometry and Topology in October 2024.

130
Louigi Addario-Berry, Pat Morin, and Ralph Neininger.
Patricia's bad distributions.
In Cécile Mailler and Sebastian Wild, editors, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2024, June 17-21, 2024, University of Bath, UK, volume 302 of LIPIcs, pages 25:1–25:8. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.

131
Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor, Gwenaël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, and David R. Wood.
The grid-minor theorem revisited.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 1241–1245, 2024.
Submitted to Advances in Combinatorics in November 2023.

132
Carla Binucci, Aaron Büngener, Giuseppe Di Battista, Walter Didimo, Vida Dujmović, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, and Alessandra Tappini.
Min-ALT=-planar drawings of graphs.
In Proceedings of the 31st International Symposium on Graph Drawing (GD 2023), 2023.
Submitted to Theoretical Computer Sciencein July 2023 and rejected in November 2023.
Submitted to Discrete Mathematics in December 2023.

133
Vida Dujmović, Louis Esperet, Pat Morin, and David R. Wood.
Proof of the clustered Hadwiger conjecture.
In Proceedings of the 64th IEEE Symposium on the Foundations of Computer Science (FOCS 2023), 2024.
Submitted to Journal of the European Mathematical Society in October 2023 and rejected in August 2024.
Submitted to Journal of the London Mathematical Society in August 2024.

134
Carla Binucci, Giuseppe Di Battista, Walter Didimo, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, and Alessandra Tappini.
Nonplanar graph drawings with ALT= vertices per face.
In Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023), volume 14093 of Lecture Notes in Computer Science, pages 86–100. Springer, 2023.

135
Prosenjit Bose, Pat Morin, and Saeed Odak.
An optimal algorithm for product structure in planar graphs.
In Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, LIPIcs, 2022.

136
Paz Carmi, Vida Dujmović, and Pat Morin.
Anagram-free chromatic number is not pathwidth-bounded.
In 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2018), 2018.

137
T. Biedl, M. Derka, V. Dujmovic, and P. Morin.
EPG-representations with small grid-size.
In Proceedings of the 25th International Symposium on Graph Drawing (GD2017), pages 184–196, 2017.

138
Greg Aloupis, Prosenjit Bose, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Karim Douïeb, Vida Dujmović, John Iacono, Stefan Langerman, and Pat Morin.
Common unfoldings of polyominoes and polycubes.
In Abstracts from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications, volume 7033 of Lecture Notes in Computer Science, pages 44–54. Springer, 2010.

139
Prosenjit Bose, Paz Carmi, Dana Jansens, Anil Maheshwari, and Michiel Smid.
Improved methods for generating quasi-Gray codes.
In Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), pages 224–235, 2010.

140
Joachim Gudmundsson and Pat Morin.
Planar visibility: Testing and counting.
In Proceedings of the Twenty-Sixth Symposium on Computational Geometry (SoCG 2010), pages 77–86, 2010.
Submitted to SIAM Journal on Computing in January 2010; rejected in July 2010.

141
Prosenjit Bose, Meng He, Anil Maheshwari, and Pat Morin.
Succinct orthogonal range search structures on a grid with applications to text indexing.
In Proceedings of the 16th International Workshop on Algorithms and Data Structures (WADS 2009), LNCS, pages 98–109. Springer, 2009.
Submitted to Computational Geometry: Theory and Applications in June 2010; rejected in February 2011.

142
Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman, and Pat Morin.
Distribution-sensitive point location in convex subdivisions.
In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pages 912–921, 2008.
Submitted to Journal of the ACM in November 2006; rejected in August 2007.
Submitted to SIAM Journal on Computing in August 2007; rejected in May 2008.

143
Prosenjit Bose, Evangelos Kranakis, Pat Morin, and Yihui Tang.
Approximate range mode and range median queries.
In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS 2005), volume 3404 of Lecture Notes in Computer Science, pages 377–388. Springer-Verlag, 2005.

144
Michel Barbeau, Evangelos Kranakis, Danny Krizanc, and Pat Morin.
Improving distance based geographic location techniques in sensor networks.
In Proceedings of the 3rd International Conference on AD-HOC Networks & Wireless (ADHOC-NOW'04), pages 197–210, 2004.

145
Prosenjit Bose, Evangelos Kranakis, Pat Morin, and Yihui Tang.
Bounds for frequency estimation of packet streams.
In Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2003), pages 33–42, 2003.

146
Vida Dujmović, Pat Morin, and David R. Wood.
Pathwidth and 3-dimensional straight-line grid drawings of graphs.
In Proceedings of the 10th International Symposium on Graph Drawing (GD2002), volume 2528 of Lecture Notes in Computer Science, pages 42–53. Springer-Verlag, 2002.

147
Stefan Langerman, Pat Morin, and Michael Soss.
Computing the maximum detour and spanning ratio of planar paths, trees and cycles.
In Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), volume 2285 of Lecture Notes in Computer Science, pages 250–261. Springer-Verlag, 2002.
Extended abstract appears at 11th Fall Workshop on Computational Geometry, 2001.

148
Prosenjit Bose and Pat Morin.
Testing the quality of manufactured balls.
In Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS'99), volume 1663 of Lecture Notes in Computer Science, pages 145–156. Springer-Verlag, 1999.

149
Prosenjit Bose and Pat Morin.
Testing the quality of manufactured disks and cylinders.
In Proceedings of the Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98), volume 1533 of Lecture Notes in Computer Science, pages 129–138. Springer-Verlag, 1998.

150
Pat Morin.
Coarse grained parallel computing on heterogeneous systems.
In Proceedings of the 1998 ACM Symposium on Applied Computing (SAC'98), pages 628–634. ACM Press, 1998.

151
Anil Maheshwari, Pat Morin, and Jörg-Rüdiger Sack.
Progressive TINs: Algorithms and applications.
In Proceedings of the 5th International Workshop on Advances in Geographic Information Systems (ACM-GIS'97), pages 24–29. ACM Press, 1997.

152
Pat Morin.
Provably secure and efficient block ciphers.
In Proceedings of the Third Annual Workshop on Selected Areas in Cryptography (SAC'96), pages 30–37, 1996.

References

153
Vida Dujmovićand Pat Morin.
Free sets in planar graphs: History and applications.
CoRR, abs/2403.17090, 2024.

154
Vida Dujmović, Pat Morin, and Saeed Odak.
Odd colourings of graph products, 2022.
[arxiv:2202.12882].

155
Prosenjit Bose, Paz Carmi, Vida Dujmović, and Pat Morin.
Near-optimal ALT=-robust geometric spanners, 2018.
[arxiv:1812.09913].

156
Vida Dujmović, Pat Morin  and David R. Wood.
Queue layouts of graphs with bounded degree and bounded genus, 2019.
[arxiv:1901.05594].

157
S. Cabello, J. Cardinal, J. Iacono, S. Langerman, P. Morin, and A. Ooms.
Encoding 3SUM.
In Proceedings of EuroCG 2019, 2019.
[arxiv:1903.02645].

158
Pat Morin and Wolfgang Mulzer.
A simple proof of Chernoff's bound, 2017.
Submitted to Symposium on Simplicity in Algorithms in August 2017 and rejected in November 2017.

159
Luc Devroye, A. Mehrabian, and Pat Morin.
First-passage percolation time on the hypercube, 2017.
Submitted to Symposium on Simplicity in Algorithms in August 2017 and rejected in November 2017.

160
Jennifer L. A. Hood and Pat Morin.
Tic tac toe, 2015.
First Place: Graph Drawing Contest 2015 (Creative Topics: Tic Tac Toe).

161
Luis Barba and Pat Morin.
Top-down skiplists.
Submitted to Algorithmica in May 2016.
Submitted to, and rejected from, SODA 2015.
Submitted to, and rejected from, ALENEX 2015.

162
John Howat, John Iacono, and Pat Morin.
The fresh-finger property.
arXiv:1302.6914.

163
Prosenjit Bose, Jean-Lou De Carufel, Pat Morin, André van Renssen, and Sander Verdonschot.
Optimal bounds on theta-graphs: More is not always better.
In The 24th Canadian Conference on Computational Geometry (CCCG 2012), pages 305–310, 2012.

164
Dan Chen and Pat Morin.
Algorithms for bivariate majority depth.
In Proceedings of the 23nd Canadian Conference on Computational Geometry (CCCG 2011), pages 425–430, 2011.

165
Evangelos Kranakis, Danny Krizanc, Pat Morin, Lata Narayanan, and Ladislav Stacho.
A tight bound on the maximum interference of random sensors in the highway model.
arXiv:1007.2120, July 2010.

166
Prosenjit Bose, Luc Devroye, Karim Douïeb, Vida Dujmović, Jamie King, and Pat Morin.
Odds-on trees.
arXiv:1002.1092, February 2010.

167
Prosenjit Bose, Luc Devroye, Karim Douïeb, Vida Dujmović, Jamie King, and Pat Morin.
Point location in disconnected planar subdivisions.
arXiv:1001.2763, January 2010.

168
Hervé Brönnimann, Jyrki Katajainen, and Pat Morin.
Putting your data structure on a diet.
Technical Report CPH-STL-2007-1, Performance Engineering Laboratory, DIKU, 2007.

169
Rossen Atanassov, Pat Morin, and Stefanie Wuhrer.
Removing outliers to minimize area and perimeter.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), 2006.

170
Prosenjit Bose, Pat Morin, Michiel Smid, and Stefanie Wuhrer.
Rotational clamshell casting in three dimensions.
Technical Report TR-06-04, Carleton University School of Computer Science, 2006.

171
Prosenjit Bose, Pat Morin, Michiel Smid, and Stefanie Wuhrer.
Rotational clamshell casting in two dimensions.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), 2006.

172
Prosenjit Bose, Luc Devroye  and Pat Morin.
Succinct data structures for approximating convex functions with applications.
In Proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG 2002), volume 2866 of LNCS, pages 97–107. Springer-Verlag, 2003.
Submitted to Journal of Discrete Algorithms in January 2005.

173
Pat Morin.
Putting your dictionary on a diet.
Technical Report TR-02-07, Carleton University School of Computer Science, November 2002.

174
Stefan Langerman and Pat Morin.
Covering points with lines (abstract).
In 11th Fall Workshop on Computational Geometry, 2001.
Results are included in Journal Paper [104].

175
Pat Morin.
Online Routing in Geometric Graphs.
PhD thesis, School of Computer Science, Carleton University, January 2001.

176
Anil Maheshwari, Pat Morin, and Jörg-Rüdiger Sack.
A framework for multiresolution modeling.
In Proceedings of the Workshop on Multiresolution Representation of 3D Geometry for Progressive Transmission, 1998.

177
Pat Morin.
Two topics in applied algorithmics.
Master's thesis, School of Computer Science, Carleton University, 1998.

178
Diane Dubrule, Pat Morin, and Jörg-Rüdiger Sack.
A parallel cartographic modelling system: Design, implementation and performance.
In GIS'97 Proceedings, pages 16–20, 1997.

179
Pat Morin.
Secure non-interactive electronic cash.
Technical Report TR-96-06, School of Computer Science, Carleton University, 1996.

References

180
Pat Morin and Subhash Suri, editors.
Algorithms and Data Structures - 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 - August 2, 2023, Proceedings, volume 14079 of Lecture Notes in Computer Science. Springer, 2023.

181
Pat Morin.
Guest editor's introduction.
Computational Geometry: Theory and Applications, 47(2):295, 2014.
Special issue of selected papers from CCCG 2008.

182
Prosenjit Bose and Pat Morin.
Guest editors' introduction.
Algorithmica, 42(1):1–2, 2005.
Special issue of selected papers from ISAAC 2002.

183
Prosenjit Bose and Pat Morin.
Guest editors' introduction.
Theory of Computing Systems, 38:251, 2005.
Special issue of selected papers from ISAAC 2002.

184
Prosenjit Bose and Pat Morin, editors.
Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2002), volume 2815 of LNCS. Springer-Verlag, 2002.

ALT=