Pat Morin's Publications As of September 22, 2014

submitted | books | chapters | journal | conference | other | edited | talks

This list is also available as a BibTeX file.

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

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

Currently Under Review

1
L. Barba and P. Morin.
Top-down skiplists.
Submitted to SODA 2015 (and rejected).
[arxiv].

2
P. Bose, J.-L. De Carufel, P. Morin, A. van Renssen, and S. Verdonschot.
Towards tight bounds on theta-graphs.
Submitted to Theoretical Computer Science in April 2014.
[arxiv].

3
V. Dujmović and P. Morin.
On obstacle numbers, 2013.
Submitted to Electronic Journal of Combinatorics in May 2014.
[arxiv].

4
V. Dujmović, P. Morin, and M. Smid.
Average stretch factor: How low does it go?
Submitted to Discrete & Computational Geometry in May 2013.
[arxiv].

5
J. Howat, J. Iacono, and P. Morin.
The fresh-finger property.
arXiv:1302.6914.
[arxiv].

Books

1
P. Morin.
Open Data Structures: An Introduction.
Athabasca University Press, Edmonton, 2013.
Also freely available as Open Data Structures (in Java) at opendatastructures.org.
[website].

2
P. Morin.
Open Data Structures (in C++).
Web, 2012.
A freely-available open content textbook.
[website].

Chapters in Books

1
P. 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
P. Bose, P. Morin, A. van Renssen, and S. Verdonschot.
The theta-5 graph is a spanner.
Computational Geometry: Theory and Applications.
Accepted in June 2014.
Preliminary version appears in Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013).
[arxiv].

2
V. Dujmović, P. Morin, and A. Sheffer.
Crossings in grid drawings.
Electronic Journal of Combinatorics, 21(1), 2014.
P1.41 (18 pages).
[arxiv] [journal].

3
P. Bose, V. Dujmović, P. Morin, and M. 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].

4
D. Chen and P. Morin.
Approximating majority depth.
Computational Geometry: Theory and Applications, 46(9):1059-1064, 2013.
Special issue of selected papers from CCCG 2012.
[arxiv].

5
D. Chen, P. Morin, and U. 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].

6
B. Ballinger, N. Benbernou, P. Bose, M. Damian, E. D. Demaine, V. Dujmović, R. Flatland, F. Hurtado, J. Iacono, A. Lubiw, P. Morin, V. Sacristán, D. Souvaine, and R. Uehara.
Coverage with $k$-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), pages Part II: 1-15, 2010.
[pdf].

7
D. Chen, O. Devillers, J. Iacono, S. Langerman, and P. 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].

8
P. Bose, K. Douïeb, V. Dujmović, J. Howat, and P. 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].

9
D. Charlton, E. D. Demaine, M. L. Demaine, V. Dujmović, P. Morin, and R. Uehara.
Ghost chimneys.
International Journal of Computational Geometry and Applications, 22(3):207-214, 2012.
Preliminary version appears in Proceedings of CCCG 2010.
[pdf].

10
S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin.
Entropy, triangulation, and point location in planar subdivisions.
ACM Transactions on Algorithms, 8(3):29:1-29:18, 2012.
[pdf] [arXiv].

11
P. Bose, K. Douïeb, and P. 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].

12
P. Bose, J. Howat, and P. 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].

13
P. Bose, E. Chen, M. He, A. Maheshwari, and P. 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].

14
D. Chen, V. Dujmović, L. Devroye, and P. 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.
[pdf][arXiv].

15
V. Dujmović, J. Howat, and P. 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].

16
V. Dujmović, J. Gudmundsson, P. Morin, and T. 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].

17
K. Buchin, M. Löffler, W. Mulzer, and P. 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].

18
E. Kranakis, D. Krizanc, and P. 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].

19
P. Bose, P. Carmi, F. Hurtado, and P. Morin.
A generalized Winternitz theorem.
Journal of Geometry, 100:29-35, 2011.
[pdf].

20
J. Gudmundsson, P. Morin, and M. Smid.
Algorithms for marketing-mix optimization.
Algorithmica, 60(4), 2011.
[pdf] [arXiv].

21
P. Bose, S. Collette, S. Langerman, A. Maheshwari, P. Morin, and M. Smid.
Sigma-local graphs.
Journal of Discrete Algorithms, 8:15-23, 2010.
[pdf].

22
L. Devroye, J. Gudmundsson, and P. Morin.
On the expected maximum degree of Gabriel and Yao graphs.
Advances in Applied Probability, 41(4):1123-1140, 2009.
[arXiv].

23
P. Bose, V. Dujmović, F. Hurtado, S. Langerman, P. Morin, and D. 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].

24
P. Bose, P. Morin, M. Smid, and S. Wuhrer.
Clamshell casting.
Algorithmica, 55(4):666-702, 2009.
Preliminary version appears in Proceedings of CAD'07.
[pdf].

25
P. Bose, V. Dujmović, F. Hurtado, and P. Morin.
Connectivity-preserving transformations of binary images.
Computer Vision and Image Understanding, 113(10):1027-1104, October 2009.
[pdf].

26
R. Atanassov, P. Bose, M. Couture, A. Maheshwari, P. Morin, M. Paquette, M. Smid, and S. Wuhrer.
Algorithms for optimal outlier removal.
Journal of Discrete Algorithms, 7:239-248, 2009.
[pdf].

27
P. Bose, P. Morin, M. Smid, and S. Wuhrer.
Rotationally monotone polygons.
Computational Geometry: Theory and Applications, 42:471-483, 2009.
See also [11].
[pdf].

28
J. Erickson, F. Hurtado, and P. Morin.
Centerpoint theorems for wedges.
Discrete Mathematics & Theoretical Computer Science, 11(1):45-54, 2009.
[pdf][note].

29
P. Bose, P. Carmi, M. Couture, A. Maheshwari, P. Morin, and M. Smid.
Spanners of complete $k$-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].

30
P. Bose, V. Dujmović, D. Krizanc, S. Langerman, P. Morin, D. R. Wood, and S. 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.
[pdf][arXiv].

31
P. Bose, H. Guo, E. Kranakis, A. Maheshwari, P. Morin, J. Morrison, M. Smid, and Y. Tang.
On the false-positive rate of Bloom filters.
Information Processing Letters, 108:210-213, 2008.
[ps.gz] [pdf].

32
P. Carmi, V. Dujmović, P. Morin, and D. R. Wood.
Distinct distances in graph drawings.
Electronic Journal of Combinatorics, 15(R107), August 2008.
[pdf].

33
D. Bremner, D. Chen, J. Iacono, S. Langerman, and P. Morin.
Output-sensitive algorithms for Tukey depth and related problems.
Statistics and Computing, 18(3):259-266, September 2008.
[pdf].

34
P. Morin.
An optimal randomized algorithm for $d$-variate zonoid depth.
Computational Geometry: Theory and Applications, 39(3):229-235, 2008.
[pdf].

35
P. K. Agarwal, R. Klein, C. Knauer, S. Langerman, P. Morin, M. Sharir, and M. 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 [15].
[ps.gz] [pdf].

36
E. D. Demaine, J. Erickson, D. Krizanc, H. Meijer, P. Morin, M. Overmars, and S. 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].

37
G. Aloupis, E. D. Demaine, S. Langerman, P. Morin, J. O'Rourke, I. Streinu, and G. 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].

38
H. Gopala and P. 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].

39
G. Aloupis, P. Bose, and P. 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].

40
P. Bose, E. D. Demaine, F. Hurtado, S. Langerman, J. Iacono, and P. 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].

41
P. Bose, A. Maheshwari, P. Morin, J. Morrison, M. Smid, and J. 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].

42
P. Bose, J. Czyzowicz, Z. Gao, P. Morin, and D. 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].

43
D. Krizanc, P. Morin, and M. 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].

44
D. Bremner, E. D. Demaine, J. Erickson, J. Iacono, S. Langerman, P. Morin, and G. 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].

45
S. Langerman and P. 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].

46
V. Dujmović, P. Morin, and D. R. Wood.
Layout of graphs with bounded tree-width.
SIAM Journal on Computing, 34(3):553-579, 2005.
[pdf] [ps.gz].

47
P. Morin and D. 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].

48
P. Bose, J. Czyzowicz, P. Morin, and D. 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].

49
P. Morin and J. 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].

50
P. Bose and P. 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].

51
P. Bose, P. Morin, and A. 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].

52
P. Bose and P. 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].

53
L. Devroye, P. Morin, and A. Viola.
On worst case Robin-Hood hashing.
SIAM Journal on Computing, 33(4):923-936, 2004.
[pdf] [ps.gz] [citeseer].

54
H. Brönnimann, J. Iacono, J. Katajainen, P. Morin, J. Morrison, and G. 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].

55
P. Bose, J. Gudmundsson, and P. 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].

56
P. Bose and P. 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].

57
M. de Berg, P. Bose, O. Cheong, and P. 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].

58
P. Bose, D. Krizanc, S. Langerman, and P. 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].

59
P. Braß, L. Heinrich-Litan, and P. 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].

60
P. Bose, M. van Kreveld, A. Maheshwari, P. Morin, and J. 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].

61
L. Devroye and P. Morin.
Cuckoo hashing: Further analysis.
Information Processing Letters, 86(4):215-219, 2003.
[pdf] [ps.gz] [note].

62
P. Bose, A. Maheshwari, and P. 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].

63
P. Bose and P. 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].

64
P. Bose, A. Brodnik, S. Carlsson, E. D. Demaine, R. Fleischer, A. López-Ortiz, P. Morin, and J. I. 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].

65
J. A. Calvo, D. Krizanc, P. Morin, M. Soss, and G. T. Toussaint.
Convexifying polygons with simple projections.
Information Processing Letters, 80(2):81-86, 2001.
[pdf] [ps.gz] [citeseer].

66
T. Fevens, A. Mesa A. Hernandez, P. Morin, M. Soss, and G. 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].

67
P. Bose, P. Morin, I. Stojmenovic, and J. 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].

68
H.-K. Ahn, P. Bose, J. Czyzowicz, N. Hanusse, E. Kranakis, and P. 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
G. Aloupis, L. Barba, P. Carmi, V. Dujmović, F. Frati, and P. Morin.
Compatible connectivity-augmentation of planar disconnected graphs.
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 2015.
[arxiv].

2
P. Bose, P. Morin, and A. van Renssen.
The price of order.
In Proceedings of the Twenty-Fifth Annual International Symposium on Algorithms and Computation (ISAAC 2014), 2014.

3
P. Bose, R. Klein, J. Howat, and P. Morin.
Biased predecessor search.
In Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN2014), pages 755-764. Springer, 2014.

4
P. Morin and S. Verdonschot.
On the average number of edges in theta graphs.
In Proceeding of the Eleventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2014), pages 121-132. SIAM, 2014.
[arxiv] [mathematica code].

5
V. Dujmović, P. Morin, and D. R. Wood.
Layered separators in minor-closed families with applications.
In Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS 2013).
[arxiv].

6
G. Aloupis, P. Bose, S. Collette, E. D. Demaine, M. L. Demaine, K. Douïeb, V. Dujmović, J. Iacono, S. Langerman, and P. 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].

7
P. Bose, P. Carmi, D. Jansens, A. Maheshwari, and M. 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.

8
J. Gudmundsson and P. Morin.
Planar visibility: Testing and counting.
In Proceedings of the Twenty-Sixth ACM Symposium on Computational Geometry (SoCG 2010), pages 77-86, 2010.
Submitted to SIAM Journal on Computing in January 2010; rejected in July 2010.
[arXiv].

9
P. Bose, M. He, A. Maheshwari, and P. 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].

10
S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. 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].

11
P. Bose, E. Kranakis, P. Morin, and Y. 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].

12
M. Barbeau, E. Kranakis, D. Krizanc, and P. 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].

13
P. Bose, E. Kranakis, P. Morin, and Y. 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].

14
V. Dujmović, P. Morin, and D. 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].

15
S. Langerman, P. Morin, and M. 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].

16
P. Bose and P. 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].

17
P. Bose and P. 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].

18
P. 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].

19
A. Maheshwari, P. Morin, and J.-R. 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].

20
P. 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
P. Bose, J.-L. De Carufel, P. Morin, A. van Renssen, and S. 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].

2
P. Bose, V. Dujmović, N. Hoda, and P. Morin.
Visibility-monotonic polygon deflation.
In The 24th Canadian Conference on Computational Geometry (CCCG 2012), pages 13-18, 2012.
Submitted to Contributions to Discrete Mathematics in June 2012.
[arxiv].

3
L. Devroye and P. Morin.
A note on interference in random point sets.
In The 24th Canadian Conference on Computational Geometry (CCCG 2012), pages 201-206, 2012.
Submitted to ACM/IEEE Transactions on Networking in March 2012 and immediately rejected.
Submitted to IEEE Transactions on Wireless Communications in March 2012 and immediately rejected.
Submitted to Wireless Networks in April 2012 and rejected in August 2012.
[arXiv].

4
D. Chen and P. Morin.
Algorithms for bivariate majority depth.
In Proceedings of the 23nd Canadian Conference on Computational Geometry (CCCG 2011), pages 425-430, 2011.
[cccg version].

5
E. Kranakis, D. Krizanc, P. Morin, L. Narayanan, and L. Stacho.
A tight bound on the maximum interference of random sensors in the highway model.
arXiv:1007.2120, July 2010.
[arXiv].

6
P. Bose, L. Devroye, K. Douïeb, V. Dujmović, J. King, and P. Morin.
Odds-on trees.
arXiv:1002.1092, February 2010.
[arXiv] [note].

7
P. Bose, L. Devroye, K. Douïeb, V. Dujmović, J. King, and P. Morin.
Point location in disconnected planar subdivisions.
arXiv:1001.2763, January 2010.
[arXiv].

8
H. Brönnimann, J. Katajainen, and P. Morin.
Putting your data structure on a diet.
Technical Report CPH-STL-2007-1, Performance Engineering Laboratory, DIKU, 2007.
[pdf].

9
R. Atanassov, P. Morin, and S. Wuhrer.
Removing outliers to minimize area and perimeter.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), 2006.
[pdf] [tech report].

10
P. Bose, P. Morin, M. Smid, and S. Wuhrer.
Rotational clamshell casting in three dimensions.
Technical Report TR-06-04, Carleton University School of Computer Science, 2006.
[pdf].

11
P. Bose, P. Morin, M. Smid, and S. Wuhrer.
Rotational clamshell casting in two dimensions.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), 2006.
[pdf].

12
P. Bose, L. Devroye and P. 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].

13
P. Morin.
Putting your dictionary on a diet.
Technical Report TR-02-07, Carleton University School of Computer Science, November 2002.
[pdf] [ps.gz].

14
S. Langerman and P. Morin.
Covering points with lines (abstract).
In 11th Fall Workshop on Computational Geometry, 2001.
Results are included in Journal Paper [45].
[pdf] [ps.gz].

15
P. Morin.
Online Routing in Geometric Graphs.
PhD thesis, School of Computer Science, Carleton University, January 2001.
[pdf] [ps].

16
A. Maheshwari, P. Morin, and J.-R. Sack.
A framework for multiresolution modeling.
In Proceedings of the Workshop on Multiresolution Representation of 3D Geometry for Progressive Transmission, 1998.
[ps.gz].

17
P. Morin.
Two topics in applied algorithmics.
Master's thesis, School of Computer Science, Carleton University, 1998.
[ps.gz] [citeseer].

18
D. Dubrule, P. Morin, and J.-R. Sack.
A parallel cartographic modelling system: Design, implementation and performance.
In GIS'97 Proceedings, pages 16-20, 1997.
[scanned pdf].

19
P. 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
P. Morin.
Guest editor's introduction.
Computational Geometry: Theory and Applications, 47(2):295, 2014.
Special issue of selected papers from CCCG 2008.

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

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

4
P. Bose and P. 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
Encoding arguments.
Probability, Combinatorics, and Geometry: Ninth Annual Workshop, April 2014.

2
Interference!
BIRS: Models of Sparse Graphs and Network Algorithms, February 2011.
[pdf] [xoj].

3
On the expected maximum degree in Yao graphs.
Dagstuhl Seminar on Geometric Networks, Metric Space Embeddings and Spatial Data Mining, November 2009.

4
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].

5
Distribution-sensitive point location.
Sydney Theory Day, May 2008.

6
Algorithms for zonoids.
East Coast Combinatorial Conference (ECCC 2007), April 2007.

7
Disctribution-sensitive point location in convex subdivisions.
Algorithms Seminar, McGill University, December 2006.

8
An optimal algorithm for $d$-variate zonoid depth.
Algorithms Seminar, Université Libre de Bruxelles, October 2006.

9
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.

10
Centerpoint theorems for wedges.
Japan Workshop on Discrete and Computational Geometry, Kanezawa, Japan, May 2005.

11
Realizing partitions respecting full and partial order information.
UPC Computational Geometry Seminar, May 2005.

12
Computing the center of area of a convex polygon.
DIMACS Workshop on Data Depth: Robust Multivariate Analysis, Computational Geometry and Applications, May 2003.

13
Output-sensitive algorithms for computing nearest-neighbour decision boundaries.
MITACS Workshop on Facility Location, Ottawa, Canada, May 2003.

14
Computing the center of area of a convex polygon.
MITACS Workshop on Facility Location, Vancouver, Canada, June 2002.

15
Two recent results on flipping polygons.
Special Session on Physical Knotting and Unknotting, AMS Spring Western Section Meeting, Las Vegas, Nevada, USA, April 2001.

16
Classifying adult content on the internet.
School of Computer Science, McGill University, June 2001.

17
Online routing in geometric networks.
SEMNET (SEMinar on NETworks), Department of Mathematics, Carleton University, November 2001.

18
Progressive TINs: Algorithms and applications.
Max-Planck-Institut für Informatik, August 1997.

19
Course-grained parallel computing on heterogeneous systems.
Oberseminar Blömer/Meyer auf der Heide: Theoretische Informatik 2. Universität-GH Paderborn, May 1997.

20
Performance evaluation with Parasol.
Real-Time and Distributed Systems Seminar. Department of Systems and Computer Engineering, Carleton University, October 1996.



Pat Morin 2014-09-22