Pat Morin's Publications

Pat Morin's Publications As of December 19, 2024

This list is also available as a BibTeX file (that includes some insider information).

Citation information is available through Google Scholar Citations and Microsoft Academic Search

More complete and correct information is available at my DBLP entry.

I also have an ORCID for whatever it's worth.

Currently Under Review

1: Vida Dujmović, Gwenaël Joret, Piotr Micek, and Pat Morin.
Erdős-pósa property of cycles that are far apart.
[arxiv:2412.13893].
2: John Iacono, Piotr Micek, Pat Morin, and Bruce Reed.
Vertex ranking of degenerate graphs.
Submitted to Random Structures & Algorithms in April 2024 and rejected in May 2024
Submitted to Electronic Journal of Combinatorics in May 2024.
[arxiv:2404.16340].
3: 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.
[arxiv:2312.03399].
4: Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh, and Pat Morin.
Asymptotically optimal vertex ranking of planar graphs.
Submitted to SODA 2021 in July 2020 and rejected in October 2020.
Submitted to Journal of Combinatorial Theory: Series B in November 2020.
Revisions requested in January 2022 and provided in August 2022.
[arxiv:2007.06455].

Books

1: Pat Morin.
Open Data Structures (in Pseudocode).
Web, 2014.
A freely-available open content textbook.
[website].
2: Pat Morin.
Open Data Structures: An Introduction.
Athabasca University Press, Edmonton, 2013.
Also freely available as Open Data Structures (in Java) at opendatastructures.org.
[website].
3: Pat Morin.
Open Data Structures (in C++).
Web, 2012.
A freely-available open content textbook.
[website].

Chapters in Books

1: Pat Morin.
Hash tables.
In Dinesh Mehta and Sartaj K. Sahni, editors, Handbook of Data Structures and Applications, chapter 9. CRC Press, 2004.
[web page].

Papers Accepted in Refereed Journals

1: 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.
Accepted in October 2024.
[arxiv:2403.06370].
2: 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.
[arxiv:2402.14181].
3: 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.
[arxiv:2212.08739][doi:10.1137/23M1591773].
4: 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.
[arxiv:2205.15096].
5: Carla Binucci, Giuseppe Di Battista, Walter Didimo, Vida Dujmović, 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.
6: 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.
[arxiv:2212.02388][doi:10.37236/11712].
7: Paz Carmi, Matthew J. Katz, and Pat Morin.
Stabbing pairwise intersecting disks by four points.
Discrete & Computational Geometry, 70:1751–1784, 2023.
[arxiv:1812.06907][doi:10.1007/s00454-023-00567-0].
8: 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.
[arxiv:2303.14970][doi:10.1017/S0963548323000275].
9: Louis Esperet, Gwenaël Joret, and Pat Morin.
Sparse universal graphs for planarity.
Journal of the London Mathematical Society, 108(4):1333–1357, 2023.
[arxiv:2010.05779][doi:10.1112/jlms.12781].
10: 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.
[arxiv:1907.05168][doi:10.1016/j.jctb.2023.03.004].
11: 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.
[arxiv:1803.03705][doi:10.1016/j.comgeo.2022.101946][doi:10.4230/LIPIcs.ICALP.2018.23].
12: Vida Dujmović and Pat Morin.
Dual circumference and collinear sets.
Discrete & Computational Geometry, 69:26–50, 2023.
[arxiv:1811.03427][doi:10.1007/s00454-022-00418-4][doi:10.4230/LIPIcs.SoCG.2019.29].
13: 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.
[arxiv:2002.05580][doi:10.1007/s00454-022-00398-5].
14: 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.
[arxiv:2105.01230][doi:10.46298/dmtcs.7458].
15: Saman Bazarghani, Paz Carmi, Vida Dujmović, and Pat Morin.
$2\times n$ grids have unbounded anagram-free chromatic number.
Electronic Journal of Combinatorics, 29(3), 2022.
[arxiv:2105.01916][doi:10.37236/10411].
16: 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.
[arxiv:2002.11721][doi:10.1017/S0963548321000213].
17: 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.
[arxiv:2011.04195][doi:10.1007/s00493-021-4585-7].
18: 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.
[doi:10.4230/LIPIcs.SoCG.2018.2].
19: 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.
[arxiv:2003.04280][doi:10.1145/3477542][video].
20: 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.
[arxiv:1811.03432][doi:10.1007/s00454-019-00167-x].
21: Pat Morin.
A fast algorithm for the product structure of planar graphs.
Algorithmica, 83(5):1544–1558, 2021.
[arxiv:2004.02530][doi:10.1007/s00453-020-00793-5][python code].
22: 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.
[arxiv:2004.03571][doi:10.7155/jgaa.00549].
23: 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.
[arxiv:1904.04791][doi:10.1109/FOCS.2019.00056][video][doi:10.1145/3385731].
24: 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.
[arxiv:1810.08314].
25: 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).
[journal version] [arxiv:1706.10193].
26: 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.
[arxiv:1707.00083] [doi:10.1002/rsa.20828].
27: 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.
[doi:10.1137/18M1214196].
28: 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.
[arxiv:1701.05639] [doi:10.1137/17M1112637].
29: 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.
[arxiv:1202.5945][doi:10.1016/j.comgeo.2017.10.006].
30: 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.
[arxiv:1611.01661] [doi:10.1007/s00453-017-0375-4].
31: 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.
[arxiv:1306.1595] [doi:10.1016/j.jctb.2017.05.006].
32: Pat Morin, Wolfgang Mulzer, and Tommy Reddad.
Encoding arguments.
ACM Computing Surveys, 50(3):46:1–36, 2017.
[arxiv:1603.08777] [doi:10.1145/3084288].
33: 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.
[arxiv:1304.3402] [mathematica code].
34: Prosenjit Bose, Vida Dujmović, Pat Morin, and Lucas Rioux-Maldague.
New bounds for facial nonrepetitive colouring.
Graphs and Combinatorics, 33(4):817–832, 2017.
[arxiv:1604.01282][doi:10.1007/s00373-017-1816-1].
35: 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).
[arxiv:1509.05053][doi:10.1145/3053370] [github].
36: Prosenjit Bose, Rolf Fagerberg, John Howat, and Pat Morin.
Biased predecessor search.
Algorithmica, 76(4):1097–1105, 2016.
Preliminary version appeared at LATIN 2014.
37: 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.
[arxiv:1404.6233][doi:10.1016/j.tcs.2015.12.017].
38: 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.
[arxiv:1602.00399a][doi:10.1142/S0218195916600013].
39: 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.
[arxiv:1408.2436][doi:10.1007/s00454-015-9716-8].
40: 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.
[PID][arxiv:1206.1982].
41: Vida Dujmović and Pat Morin.
On obstacle numbers.
Electronic Journal of Combinatorics, 22(3), 2015.
P3.1 (7 pages).
[journal version][arxiv:1308.4321].
42: Vida Dujmović, Pat Morin, and Michiel Smid.
Average stretch factor: How low does it go?
Discrete & Computational Geometry, 53(2):296–326, 2015.
[arxiv:1305.4170][doi:10.1007/s00454-015-9663-4].
43: Prosenjit Bose, Pat Morin, André van Renssen, and Sander Verdonschot.
The $\Theta_5$ 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).
[arxiv:1212.0570][doi:10.1016/j.comgeo.2012.04.004].
44: Vida Dujmović, Pat Morin, and Adam Sheffer.
Crossings in grid drawings.
Electronic Journal of Combinatorics, 21(1), 2014.
P1.41 (18 pages).
[journal version] [arxiv:1301.0303].
45: 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.
[arxiv:1204.4679][doi:10.1137/120874473].
46: 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.
[arxiv:1205.1524][doi:10.1016/j.comgeo.2013.06.005].
47: 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.
[pdf][doi:10.1016/j.comgeo.2012.03.001].
48: 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 -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.
[pdf][doi:10.1007/s10878-012-9475-x].
49: 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.
[pdf][doi:10.1016/j.comgeo.2012.04.004].
50: 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.
[pdf][doi:10.1016/j.comgeo.2012.01.002].
51: 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.
[pdf][doi:10.1142/S0218195912500057].
52: 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.
[arxiv:0901.1908][doi:10.1145/2229163.2229173].
53: 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).
[pdf][doi:10.1016/j.jda.2011.12.017].
54: 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.
[pdf][doi:10.1016/j.jda.2011.11.003].
55: 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.
[arxiv:0805.4147].
56: 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.
[arxiv:0911.2484][doi:10.1016/j.comgeo.2011.12.005].
57: 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.
[arxiv:0806.2707][doi:10.1007/s00453-010-9440-y].
58: 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).
[website][arxiv:0908.3545].
59: 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.
[springerlink].
60: 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.
[pdf].
61: Prosenjit Bose, Paz Carmi, Ferran Hurtado, and Pat Morin.
A generalized Winternitz theorem.
Journal of Geometry, 100:29–35, 2011.
[pdf].
62: Joachim Gudmundsson, Pat Morin, and Michiel Smid.
Algorithms for marketing-mix optimization.
Algorithmica, 60(4), 2011.
[pdf] [arxiv:0903.0308].
63: 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.
[pdf].
64: 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.
[arxiv:0905.3584].
65: 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).
[arxiv:0710.1641].
66: 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.
[pdf].
67: 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.
[pdf].
68: 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.
[pdf].
69: Prosenjit Bose, Pat Morin, Michiel Smid, and Stefanie Wuhrer.
Rotationally monotone polygons.
Computational Geometry: Theory and Applications, 42:471–483, 2009.
See also [18].
[pdf].
70: Jeff Erickson, Ferran Hurtado, and Pat Morin.
Centerpoint theorems for wedges.
Discrete Mathematics & Theoretical Computer Science, 11(1):45–54, 2009.
[pdf][note].
71: Prosenjit Bose, Paz Carmi, Matthieu Couture, Anil Maheshwari, Pat Morin, and Michiel Smid.
Spanners of complete -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.
[pdf].
72: 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.
[arxiv:cs/0605011].
73: 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.
[ps.gz] [pdf].
74: Paz Carmi, Vida Dujmović, Pat Morin, and David R. Wood.
Distinct distances in graph drawings.
Electronic Journal of Combinatorics, 15(R107), August 2008.
[pdf].
75: 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.
[pdf].
76: Pat Morin.
An optimal randomized algorithm for -variate zonoid depth.
Computational Geometry: Theory and Applications, 39(3):229–235, 2008.
[pdf].
77: 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 [20].
[ps.gz] [pdf].
78: 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.
[ps.gz] [pdf].
79: 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.
[pdf].
80: 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).
[pdf].
81: 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.
[ps.gz] [pdf].
82: 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.
[ps.gz] [pdf] [citeseer].
83: 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).
[ps.gz] [pdf].
84: 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.
[pdf].
85: 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.
[pdf] [ps.gz].
86: 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.
[pdf] [ps.gz] [citeseer].
87: 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.
[pdf] [ps.gz] [correction].
88: Vida Dujmović, Pat Morin, and David R. Wood.
Layout of graphs with bounded tree-width.
SIAM Journal on Computing, 34(3):553–579, 2005.
[pdf] [ps.gz].
89: 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).
[ps.gz] [pdf] [slides].
90: 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).
[pdf] [ps.gz] [citeseer].
91: 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).
[pdf] [ps.gz] [citeseer].
92: 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.
[pdf] [ps.gz] [citeseer].
93: 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.
[pdf] [ps.gz] [citeseer].
94: 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.
[pdf] [ps.gz] [citeseer] [source code].
95: Luc Devroye, Pat Morin, and Alfredo Viola.
On worst case Robin-Hood hashing.
SIAM Journal on Computing, 33(4):923–936, 2004.
[pdf] [ps.gz] [citeseer].
96: 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).
[pdf] [ps.gz] [source].
97: 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).
[ps.gz] [pdf] [citeseer].
98: 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).
[pdf] [ps.gz].
99: 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).
[pdf] [ps.gz] [citeseer].
100: 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).
[pdf] [ps.gz] [citeseer].
101: 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.
[pdf] [ps.gz] [slides].
102: 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.
[pdf] [ps.gz] [citeseer].
103: Luc Devroye and Pat Morin.
Cuckoo hashing: Further analysis.
Information Processing Letters, 86(4):215–219, 2003.
[pdf] [ps.gz] [note].
104: 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.
[pdf] [ps.gz] [citeseer].
105: 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).
[pdf] [ps.gz] [citeseer] [source code].
106: 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).
[pdf] [ps.gz] [citeseer].
107: 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.
[pdf] [ps.gz] [citeseer].
108: 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.
[pdf] [ps.gz].
109: 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).
[pdf] [ps.gz] [citeseer] [source code].
110: 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).
[pdf] [ps.gz] [citeseer].

Papers Accepted at Refereed Conferences

1: Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood.
Planar graphs in blowups of fans.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2025).
[arxiv:2407.05936].
2: 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).
[arxiv:2311.16953].
3: Louigi Addario-Berry, Pat Morin, and Ralph Neininger.
Patricia's bad distributions.
In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024).
[arxiv:2403.05269].
4: 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.
[arxiv:2307.02816].
5: 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--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.
6: 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).
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.
[arxiv:2306.06224].
7: Carla Binucci, Giuseppe Di Battista, Walter Didimo, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, and Alessandra Tappini.
Nonplanar graph drawings with 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.
[doi:10.1007/978-3-031-43380-1_7].
8: 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.
[arxiv:2202.08870] [doi:10.4230/LIPIcs.SWAT.2022.19].
9: 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.
[arxiv:1802.01646].
10: T. Biedl, M. Derka, V. Dujmović, and P. Morin.
EPG-representations with small grid-size.
In Proceedings of the 25th International Symposium on Graph Drawing (GD2017), pages 184–196, 2017.
[arxiv:1708.09749].
11: 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.
[pdf].
12: 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.
[arxiv].
13: 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.
[arXiv].
14: 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.
[pdf].
15: 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.
[pdf].
16: 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.
© Springer-Verlag, [pdf].
17: 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.
[ps.gz] [pdf].
18: 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.
[pdf] [ps.gz].
19: 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.
© Springer-Verlag, [pdf] [ps.gz] [citeseer].
20: 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.
© Springer-Verlag, [pdf] [ps.gz].
21: 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.
© Springer-Verlag, [pdf] [ps.gz] [citeseer].
22: 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.
© Springer-Verlag, [pdf] [ps.gz] [citeseer].
23: 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.
© ACM, [short pdf] [short ps.gz] [long pdf] [long ps.gz] [citeseer].
24: 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.
© ACM, [short pdf] [short ps.gz] [long pdf] [long ps.gz].
25: 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.
[pdf] [ps.gz].

Other Contributions

1: Vida Dujmović, Pat Morin, and Saeed Odak.
Odd colourings of graph products, 2022.
[arxiv:2202.12882].
2: Prosenjit Bose, Paz Carmi, Vida Dujmović, and Pat Morin.
Near-optimal -robust geometric spanners, 2018.
[arxiv:1812.09913].
3: Vida Dujmović, Pat Morin and David R. Wood.
Queue layouts of graphs with bounded degree and bounded genus, 2019.
[arxiv:1901.05594].
4: S. Cabello, J. Cardinal, J. Iacono, S. Langerman, P. Morin, and A. Ooms.
Encoding 3SUM.
In Proceedings of EuroCG 2019, 2019.
[arxiv:1903.02645].
5: 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.
[pdf].
6: 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.
[pdf].
7: Jennifer L. A. Hood and Pat Morin.
Tic tac toe, 2015.
First Place: Graph Drawing Contest 2015 (Creative Topics: Tic Tac Toe).
[a1 pdf][text].
8: 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.
[arxiv].
9: John Howat, John Iacono, and Pat Morin.
The fresh-finger property.
arXiv:1302.6914.
[arxiv].
10: 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.
[pdf].
11: 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.
[cccg version].
12: 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.
[arXiv].
13: Prosenjit Bose, Luc Devroye, Karim Douïeb, Vida Dujmović, Jamie King, and Pat Morin.
Odds-on trees.
arXiv:1002.1092, February 2010.
[arXiv] [note].
14: 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.
[arXiv].
15: 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.
[pdf].
16: 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.
[pdf] [tech report].
17: 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.
[pdf].
18: 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.
[pdf].
19: 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.
© Springer-Verlag, [short pdf] [short ps.gz] [long pdf] [long ps.gz].
20: Pat Morin.
Putting your dictionary on a diet.
Technical Report TR-02-07, Carleton University School of Computer Science, November 2002.
[pdf] [ps.gz].
21: Stefan Langerman and Pat Morin.
Covering points with lines (abstract).
In 11th Fall Workshop on Computational Geometry, 2001.
Results are included in Journal Paper [87].
[pdf] [ps.gz].
22: Pat Morin.
Online Routing in Geometric Graphs.
PhD thesis, School of Computer Science, Carleton University, January 2001.
[pdf] [ps].
23: 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.
[ps.gz].
24: Pat Morin.
Two topics in applied algorithmics.
Master's thesis, School of Computer Science, Carleton University, 1998.
[ps.gz] [citeseer].
25: 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.
[scanned pdf].
26: Pat Morin.
Secure non-interactive electronic cash.
Technical Report TR-96-06, School of Computer Science, Carleton University, 1996.
[ps.gz].

Edited Volumes and Journal Issues

1: 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.
2: Pat Morin.
Guest editor's introduction.
Computational Geometry: Theory and Applications, 47(2):295, 2014.
Special issue of selected papers from CCCG 2008.
3: Prosenjit Bose and Pat Morin.
Guest editors' introduction.
Algorithmica, 42(1):1–2, 2005.
Special issue of selected papers from ISAAC 2002.
4: Prosenjit Bose and Pat Morin.
Guest editors' introduction.
Theory of Computing Systems, 38:251, 2005.
Special issue of selected papers from ISAAC 2002.
5: 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.

Invited Talks

1: Linear versus centered colouring.
AlgoLUNCH seminar, May 2023.
2: Proof of the clustered Hadwiger conjecture.
Jagiellonian TCS seminar, March 2023.
3: Linear colouring, centered colouring, treedepth, treewidth, and grids.
Séminaire de Mathématiques Discrètes, March 2023.
4: Free sets in planar graphs.
Jagiellonian TCS seminar, March 2022.
5: What is computer science?
YSBC Software Technology Conference, May 2021.
6: Growing a spanning tree of a graph.
IMPA Probability and Combinatorics Seminar, February 2017.
7: Turán-type theorems for triangles in convex point sets.
Shonan-Village Meeting on Geometric Optimization, May 2016.
8: Turán-type theorems for triangles in convex point sets.
Courant Institute Geometry Seminar, April 2016.
9: Encoding arguments.
Probability, Combinatorics, and Geometry: Ninth Annual Workshop, April 2014.
10: Interference!
BIRS: Models of Sparse Graphs and Network Algorithms, February 2011.
[pdf] [xoj].
11: On the expected maximum degree in Yao graphs.
Dagstuhl Seminar on Geometric Networks, Metric Space Embeddings and Spatial Data Mining, November 2009.
12: Randomized algorithms I, II, and III.
New Zealand Institute of Mathematics and its Applications. Programme in Algorithmics, December 2008.
[pdf i] [pdf ii] [pdf iii].
13: Distribution-sensitive point location.
Sydney Theory Day, May 2008.
14: Algorithms for zonoids.
East Coast Combinatorial Conference (ECCC 2007), April 2007.
15: Disctribution-sensitive point location in convex subdivisions.
Algorithms Seminar, McGill University, December 2006.
16: An optimal algorithm for -variate zonoid depth.
Algorithms Seminar, Université Libre de Bruxelles, October 2006.
17: Recent results on data depth and outlier removal in 2d.
Radcliffe Institute Seminar on Computational Aspects of Statistical Data Depth Analysis, Cambridge, MA, USA, July 2006.
18: Centerpoint theorems for wedges.
Japan Workshop on Discrete and Computational Geometry, Kanezawa, Japan, May 2005.
19: Realizing partitions respecting full and partial order information.
UPC Computational Geometry Seminar, May 2005.
20: Computing the center of area of a convex polygon.
DIMACS Workshop on Data Depth: Robust Multivariate Analysis, Computational Geometry and Applications, May 2003.
21: Output-sensitive algorithms for computing nearest-neighbour decision boundaries.
MITACS Workshop on Facility Location, Ottawa, Canada, May 2003.
22: Computing the center of area of a convex polygon.
MITACS Workshop on Facility Location, Vancouver, Canada, June 2002.
23: Two recent results on flipping polygons.
Special Session on Physical Knotting and Unknotting, AMS Spring Western Section Meeting, Las Vegas, Nevada, USA, April 2001.
24: Classifying adult content on the internet.
School of Computer Science, McGill University, June 2001.
25: Online routing in geometric networks.
SEMNET (SEMinar on NETworks), Department of Mathematics, Carleton University, November 2001.
26: Progressive TINs: Algorithms and applications.
Max-Planck-Institut für Informatik, August 1997.
27: Course-grained parallel computing on heterogeneous systems.
Oberseminar Blömer/Meyer auf der Heide: Theoretische Informatik 2. Universität-GH Paderborn, May 1997.
28: Performance evaluation with Parasol.
Real-Time and Distributed Systems Seminar. Department of Systems and Computer Engineering, Carleton University, October 1996.